资源描述：
《3路径、最短路径、最大流》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、路径、最短路径、最大流----图论畅想与matlab编程简化假设：图都是连通的。1无权图中单点到单点的路径1.1示例数据：迷宫邻接矩阵：MG(i,j)表示顶点i与顶点j的邻接关系。迷宫A迷宫B迷宫C迷宫DMG=[0,0,1,1,1,1,11,0,1,1,1,1,11,0,0,0,1,0,01,1,1,0,1,1,01,1,1,0,1,1,01,1,1,0,0,0,01,1,1,1,1,1,01,1,1,1,1,1,0];MG=[0,0,1,1,1,1,11,0,1,1,1,1,11,0,0,0,1,0,01,1,1,0,1,1,01,1
2、,1,0,1,1,01,1,1,0,0,0,01,1,1,1,1,1,11,1,1,1,1,1,1];MG=[0,0,1,1,1,1,11,0,1,1,1,1,11,0,0,0,0,0,01,1,1,0,1,1,01,1,1,0,1,1,01,1,1,0,0,0,01,1,1,0,1,1,11,1,1,0,0,0,0];MG=[0,0,1,1,1,1,11,0,1,1,1,1,11,0,0,0,0,0,01,1,1,0,1,1,01,1,1,0,1,1,01,1,1,0,0,0,01,1,1,0,1,1,01,1,1,0,0,0,0];
3、1.2求一条简单路径（有误）functionpath=findMGPath(MG,s,t)[m,n]=size(MG);FS=[0,1;1,0;0,-1;-1,0];%东南西北path=[s0];%路径栈栈顶值:[110]while~isempty(path)path%调试语句%从栈顶取出当前位置loc，访问过的方向编号floc=path(end,1:2);f=path(end,3);iff==4path(end,:)=[];%尝试了所有的方向之后，出栈elsepath(end,3)=f+1;nextloc=loc+FS(f+1,:);
4、%下一步的位置nextlocifnextloc(1)>=1&nextloc(1)<=m&nextloc(2)>=1&nextloc(2)<=n&MG(nextloc(1),nextloc(2))==0path=[path;nextloc0];%进栈ifnextloc(1)==t(1)&nextloc(2)==t(2)path=path(:,1:2);return;endendendendend分析：迷宫A、迷宫D，找出一条路径。迷宫B、迷宫C，陷入死循环！原因：未考虑走回头路的可能性！1.3求一条简单路径（检查足迹）functionpa
5、th=findMGPath(MG,s,t)[m,n]=size(MG);FS=[0,1;1,0;0,-1;-1,0];%东南西北path=[s0];%路径栈栈顶值:[110]while~isempty(path)path%调试语句%从栈顶取出当前位置loc，访问过的方向编号floc=path(end,1:2);f=path(end,3);iff==4path(end,:)=[];%尝试了所有的方向之后，出栈elsepath(end,3)=f+1;nextloc=loc+FS(f+1,:);%下一步的位置nextlocifnextloc(
6、1)>=1&nextloc(1)<=m&nextloc(2)>=1&nextloc(2)<=n&MG(nextloc(1),nextloc(2))==0&isIn(path,nextloc)==0path=[path;nextloc0];%进栈ifnextloc(1)==t(1)&nextloc(2)==t(2)path=path(:,1:2);return;endendendendendfunctionF=isIn(path,loc)fori=1:size(path,1)ifpath(i,1)==loc(1)&path(i,2)==l
7、oc(2)F=1;return;endendF=0;end分析：迷宫A、迷宫B、迷宫C、迷宫D，找出一条路径，但未必是最短路径。归纳：图缺少明确的层次性，在遍历时，完全有可能访问已经访问过的顶点（位置/状态）。思考：有无其他检查足迹的方法？当然有！1.4求所有简单路径functionfindMGPaths(MG,s,t)[m,n]=size(MG);FS=[0,1;1,0;0,-1;-1,0];%东南西北path=[s0];%路径栈栈顶值:[110]while~isempty(path)%从栈顶取出当前位置loc，访问过的方向编号flo
8、c=path(end,1:2);f=path(end,3);iff==4path(end,:)=[];%尝试了所有的方向之后，出栈elsepath(end,3)=f+1;nextloc=loc+FS(f+1
