3路径、最短路径、最大流.doc

路径、最短路径、最大流 -图论畅想与matlab编程简化假设：图都是连通的。1 无权图中单点到单点的路径1.1 示例数据：迷宫邻接矩阵：MG(i,j)表示顶点i与顶点j的邻接关系。迷宫A迷宫B迷宫C迷宫DMG= 0,0,1,1,1,1,1 1,0,1,1,1,1,1 1,0,0,0,1,0,0 1,1,1,0,1,1,0 1,1,1,0,1,1,0 1,1,1,0,0,0,0 1,1,1,1,1,1,0 1,1,1,1,1,1,0;MG= 0,0,1,1,1,1,1 1,0,1,1,1,1,1 1,0,0,0,1,0,0 1,1,1,0,1,1,0 1,1,1,0,1,1,0 1,1,1,0,0,0,0 1,1,1,1,1,1,1 1,1,1,1,1,1,1;MG= 0,0,1,1,1,1,1 1,0,1,1,1,1,1 1,0,0,0,0,0,0 1,1,1,0,1,1,0 1,1,1,0,1,1,0 1,1,1,0,0,0,0 1,1,1,0,1,1,1 1,1,1,0,0,0,0;MG= 0,0,1,1,1,1,1 1,0,1,1,1,1,1 1,0,0,0,0,0,0 1,1,1,0,1,1,0 1,1,1,0,1,1,0 1,1,1,0,0,0,0 1,1,1,0,1,1,0 1,1,1,0,0,0,0;1.2 求一条简单路径（有误）function path=findMGPath(MG,s,t) m,n=size(MG); FS=0,1; 1,0; 0,-1; -1,0; %东南西北 path=s 0; % 路径栈 栈顶值:1 1 0 while isempty(path) path % 调试语句 % 从栈顶取出当前位置loc，访问过的方向编号f loc=path(end,1:2); f=path(end,3); if f=4 path(end,:)=; % 尝试了所有的方向之后，出栈 else path(end,3)=f+1; nextloc=loc+FS(f+1,:); % 下一步的位置nextloc if nextloc(1)=1 & nextloc(1)=1 & nextloc(2)=1 & nextloc(1)=1 & nextloc(2)=1 & nextloc(1)=1 & nextloc(2)0)+f; % +f 细节决定胜负 if isempty(adjv) path(end,:)=; % 尝试了所有邻接点后，出栈 else nextadjv=adjv(1); % 下一个邻接点adjv path(end,2)=nextadjv; if isempty(find(path(:,1)=nextadjv) %检查足迹 path=path; nextadjv 0; % 进栈 if nextadjv=t % 找到了终点 path=path(:,1); return; end end end endend测试：path=FindPath(G, 1, 6) 有路径测试：path=FindPath(G, 1, 8) 无路径2.3 思考：从起点到终点的所有路径2.4 从起点到终点的路径（递归算法）function testPathglobal G path pathsG=0 3 2 0 0 0 0 0 1 3 4 0 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 0 0 3 0 0 0 0 0 0 ;paths=; path=;FindPath(1, 6);pathsendfunction FindPath(s, t); global G path paths path=path; s; % 进栈 if s=t paths(end+1).path=path % 保存所有路径 else adjv=find(G(s,:)0); % 所有的邻接点 for i=1:length(adjv) if isempty(find(path=adjv(i) % 以未被访问过的邻接点为起点，进行深度优先搜索 FindPath(adjv(i), t); end end end path(end)=; % 出栈end 算法检验：所求路径中当然没有回路！有向无环图有向有环图所有路径1,2,3,5,61,2,4,61,2,5,61,3,5,6所有路径1,2,3,5,61,2,4,61,2,5,61,3,5,2,4,61,3,5,63 归纳与提高3.1 归纳图的遍历的功能：从指定顶点出发，遍历图中每个顶点。深度优先搜索DFS算法的特征是：以未被访问过的邻接点为起点，进行DFS。核心数据结构：栈。实现形式：可递归，可非递归。3.2 提高：欧拉回路算法步骤：1、利用DFS，从图中求得任一回路；若无回路，则原图非欧拉图；2、从图中删掉回路中的边；3、若图中的边集不为空，转步骤1，否则转步骤4；4、组合所有的回路，即得到欧拉回路。C1=5 1 2 5C2=3 2 4 6 3C3=8 7 4 1 3 8 练习1：将上述DFS函数改为求一条回路的函数。 练习2：如何将上述C1、C2、C3合并为一条回路。4 单点到多点的最短路径算法4.1 无权图的最短路径算法 计算从v3到其余各个顶点的最短路径。function testBFSG=0 1 0 1 0 0 00 0 0 1 1 0 01 0 0 0 0 1 00 0 1 0 1 1 10 0 0 0 0 0 10 0 0 0 0 0 00 0 0 0 0 1 0;sd=BFS(G, 3) % sd=1 2 0 2 3 1 3end广度优先搜索BFS算法的特征是：从起点由近及远，访问未被访问过的顶点。核心数据结构：队列。% 队列的示例：% 3 1 6 2 % 第1行是节点下标， % 0 1 1 2 % 第2行是节点对应的最短路径长度每个顶点只能进一次队列。同样要防备顶点重复进队列。引入标志向量flag。flag(i)=0表示顶点i未进队列flag(i)=1表示顶点i已进队列function sd=BFS(G,sv) n=size(G,1); flag=zeros(1, n); % 标志向量 sd=ones(1,n)*inf; sd(sv)=0; % 初始化sd为inf inf 0 inf inf inf inf Q=sv; 0; flag(sv)=1; % 队列Q初始化 while isempty(Q) v=Q(1,1); d=Q(2,1); sd(v)=d; % 填写最短路径长度 Q(:,1)=; % 出队列 adjv=find(G(v,:)=1); % 找到v的所有邻接点adjv adjv=adjv(find(flag(adjv)=0); % adjv没有进过队列的邻接点 adjvsd=ones(1,length(adjv) * (d+1); Q=Q(1,:) adjv; Q(2,:) adjvsd; % 进队列 flag(adjv)=1; endend思考：只求出了最短路径长度，如何表示、计算最短路径？4.2 带非负权图的最短路径Dijkstra算法：基于贪心规则，从起点由近及远，利用三角不等式，逐步修正从起点到各个顶点的最短路径。标志向量Finish，表示对应顶点的最短路径长度已经确定。Cost=0,Inf,10,Inf,30,100; Inf,0,5,Inf,Inf,Inf; Inf,Inf,0,50,Inf,Inf; Inf,Inf,Inf,0,Inf,10; Inf,Inf,Inf,20,0,60; Inf,Inf,Inf,Inf,Inf,0 ;sv=1;Dist, Path = Dijkstra(Cost,sv)for ev=1:length(Path) Display(Path,sv,ev)end计算最短路径长度，并保存每个最短路径中的上一个顶点。function Dist, Path = Dijkstra(Cost,StartV) n=size(Cost,1); % 顶点个数 Dist=Cost(StartV,:); % 路径长度初始化为邻边长度 Path=zeros(1,n); % 路径初始化为全0 Finish=zeros(1,n); Finish(StartV)=1; for i=1: n-1 w=MinCost(Dist,Finish); % 最近的邻接点w(尚未确定最短距离) if(w=0 ) return; end; Finish(w)=1; for j=1:n if(Finish(j)=0 & Dist(w)+Cost(w,j)Dist(j) % 三角不等式 Dist(j)=Dist(w)+Cost(w,j); Path(j)=w; % 只记住到达j之前的中间顶点 end end endend% 查找Finish(i)=0的Dist(i)中的最小值的下标function imin = MinCost(Dist, Finish) min=inf; imin=0; for i=1:length(Dist) if(Finish(i)=0 & Dist(i)ev的顶点序列function pathv=Display(Path,sv,ev) v=ev; pathv=v; while Path(v)0 v=Path(v); pathv=v pathv; end pathv=sv pathv;end4.3 带负权图的最短路径 思考：能否有最省事的方法求解带负权图的最短路径？function testNegBFSG=0 2 -2 0 0 0 0 0 0 0 0 2 0 1 0 0; % -10 1 0 0; sd=NegBFS(G, 1) %sd=0 1 -2 0endBellman Ford算法：基于穷举的思路，从起点由近及远，利用三角不等式，逐步修正从起点到各个顶点的最短路径。算法框架：利用BFS算法的框架，实现穷举所有邻接边的效果。标志向量flag，表示对应顶点是否进过队列，而非路径长度已经确定。function sd=NegBFS(G,sv) n=size(G,1); flag=zeros(1, n); sd=ones(1,n)*inf; sd(sv)=0; % 初始化sd为0 inf inf inf Q=sv; flag(sv)=1; % 队列Q初始化 while isempty(Q) v=Q(1); Q(1)=; % 出队列 adjv=find(G(v,:)=0); % 找到v的所有邻接点adjv for i=1:length(adjv) w=adjv(i); % 邻接点的下标w if sd(v)+G(v,w)t的最大流量。function testFlowG=0 3 2 0 0 0 0 0 1 3 4 0 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 0 0 3 0 0 0 0 0 0 ;mount=Flow(G, 1, 6) % mount=5end6.2 网络流的算法6.2.1 算法思路1、找到从s-t的一条路径2、找到该路径的流量（组成各边流量的最小值）3、从图中删除该流量4、重复步骤1至3，直至s-t无路径。6.2.2 演算示例示例1：第1条路径第2条路径第3条路径依次找到的路径删除路径流量后的剩余图思考：太简洁了，似乎有点不安全感。问：路径的次序如何定义？不同的次序对结果有无影响？示例2： 找到的第1条路径删除路径流量后的剩余图6.2.3 演算改进与细化 深入理解有向图的结构：有向图存储结构G=0 3 2 0 0 0 0 0 1 3 4 0 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 0 0 3 0 0 0 0 0 0 ;示例：第1条路径第2条路径依次找到的路径删除路径流量后的剩余图6.2.4 算法实现function mount=Flow(G, s, t); mount=0 % 总流量 while 1 G path=FindPath(G, s, t); % 1 2 3 5 6 if isempty(path) break; end vs=path(1:end-1) path