matlab计算最短路径

1、湖南大学湖南大学MATLAB实训报告目：matlab计算最短路径问题学院名称：信息科学与工程学院专业班级：软件工程四班学生姓名：彭天越学 号：20112601416日 期：2013年7月3号湖南大学目录题目 2问题描述 3(1) 根据无向图A,使用Di.jistra 算法 3(2) 根据有向图B,使用 Warshall-Floyd 算法 4思路及代码 4(1) 思路 4(2) 源代码 5测试结果说明 10(1) Di.jistra算法 10(2) Floyd 算法 11小结 11题巨求下图中顶点 折到顶点31的最短距离和最短路(2学分)VIIA无向囹3B.有向图问题描述(1)根据无向图A,使用

2、Di.jistra算法V11A无向囹湖南大学城用布火乡7根据有向图,使用 Warshall-Floyd 算法思路及代码思路(1) Dijkstra 算法使用范围：1) 寻求从一固定顶点到其余各点的最短路径；2) 有向图、无向图和混合图；3) 权非负.算法思路：采用标号作业法，每次迭代产生一个永久标号，从而生长一颗 以Vo为根的最短路树，在这颗树上每个顶点与根节点之间的路径皆为最短路径 . 诉法步骤：S:具有永久标号的顶点集；l(v): V 的标记；f(v):v 的父顶点，用以确定最短路径；输入加权图的带权邻接矩阵 W=W(Vi,Vj) nxm.1) 初始化 令 l(v o)=O,S=p V V

3、#Vo ,l(v)=°°；2) 更新 l(v), f(v)寻找不在S中的顶点u,使l(u)为最小.把u加入到S中，然后对所有不在S中的 顶点 v,如 l(v)>l(u)+w(u,v),贝U 更新 l(v),f(v), 即l(v)，l(u)+w(u,v),f(v)' u；3) 重复步骤2),直到所有顶点都在S中为止.(2) Floyd 算法使用范围：1) 求每对顶点的最短路径；2) 有向图、无向图和混合图；邕)浙槌4算法思想：直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D(1),D(2),，D(n), D(n)是图的距离矩阵，同时引入一个后继

4、点矩阵记录两点间的 最短路径.算法步骤：d(i,j) : i 到j的距离；path(i,j): i 到j的路径上i的后继点；输入带权邻接矩阵a(i,j).1) 赋初值对所有 i,j, d(i,j) - a(i,j) , path(i,j) - j,k=l.2) 更新 d(i,j) , path(i,j)对所有 i,j,若 d(i,k)+d(k,j)<d(i,j),贝Ud(i,j), d(i,k)+d(k,j) , path(i,j) , path(i,k) , k , k+13) 重复2)直到k=n+1(2)源代码(1) Dijkstra.m 文件咐算最短路径(Dijkstra 算法)%

5、min表示最短的距离%path表示最短路径%wK示邻接矩阵%start表示开始点%terminal表示终止点function min,path=dijkstra(w,start,terminal)n=size(w,1); % 计算邻接矩阵的行数label(start)=0; f(start)=start;%初始化for i=1:nif i=startlabel(i)=inf;endends(1)=start; u=start;咖新最短路径直到所有顶点都遍历while length(s)<nfor i=1:nins=0;for j=1:length(s)if i=s(j)ins=1;end

6、endif ins=0v=i;if label(v)>(label(u)+w(u,v)label(v)=(label(u)+w(u,v);f(v)=u;endendend%v1=0;k=inf;for i=1:nins=0;for j=1:length(s)if i=s(j)ins=1;endendif ins=0v=i;if k>label(v)k=label(v);v1=v;endendends(length(s)+1)=v1;u=v1;end%求出最短距离与最短路径min=label(terminal); path(1)=terminal; i=1;while path(i)

7、=startpath(i+1)=f(path(i);i=i+1 ;endpath(i)=start;L=length(path);path=path(L:-1:1);% 循环输出路径text01.m脚本文件进行测试clear;clc;fprintf('计算最短路径(Dijkstra 算法)n');x=0,2,1,8,inf,inf,inf,inf,inf,inf,inf;2,0,inf,6,1,inf,inf,inf,inf,inf,inf;1,inf,0,7,inf,inf,9,inf,inf,inf,inf;8,6,7,0,5,1,2,inf,inf,inf,inf;inf

8、,1,inf,5,0,3,inf,2,1,inf,inf;inf,inf,inf,1,3,0,4,inf,6,inf,inf;inf,inf,9,2,inf,4,0,inf,3,1,inf;inf,inf,inf,inf,2,inf,inf,0,7,inf,inf;inf,inf,inf,inf,inf,6,3,7,0,1,2;inf,inf,inf,inf,inf,inf,1,inf,1,0,1;inf,inf,inf,inf,inf,inf,inf,inf,2,1,0%x=input('输入邻接矩阵:');start=input('输入起点：)；terminal=i

9、nput('输入终点：');fprintf('计算结果如下：');min,path_way=dijkstra(x,start,terminal)Floyd.m 函数以的算最短路径(Floyd算法)%D,path,min1,path1=floyd(a,start,terminal) 返回矩阵 D, path; 并返回 start 与terminal之间的最短距离 min 1和最短路径path1.%path(i,j):表示i到j的路径上i的后继点；%D(i,j):表示i到j的距离；以输入带权邻接矩阵a(i,j).%1赋初值%对所有 i,j, D(i,j)<-a

10、(i,j) , path(i,j)<-j湖南大学%2 更新 D(i,j) , path(i,j)%对所有 i,j, 若 D(i,k)+D(k,j)<d(i,j), 则%D(i,j)<-D(i,k)+D(k,j) , path(i,j)<-path(i,k) , k<-k+1%3重复2)直到k=n+1function D,path,min1,path1=floyd(a,start,terminal) D=a;n=size(D,1);path=zeros(n,n);% 初女台化for i=1:nfor j=1:n if D(i,j)=inf path(i,j)=j;e

11、ndendendfor k=1:nfor i=1:nfor j=1:nif D(i,k)+D(k,j)<D(i,j) D(i,j)=D(i,k)+D(k,j);path(i,j)=path(i,k);endendendendif nargin=3% 参数个数为3的时候执行min1=D(start,terminal);%最短距离m(1)=start;i=1;path1= ; %计算最短路径while path(m(i),terminal)=terminalk=i+1;m(k)=path(m(i),terminal);i=i+1;endm(i+1)=terminal;path1=m;endt

12、ext02.m脚本文件，进行测试clear;clc;fprintf（'计算最短路径（Floyd算法）n'）;x=0,2,inf,8,inf,inf,inf,inf,inf,inf,inf;inf,0,inf,6,1,inf,inf,inf,inf,inf,inf;1,inf,0,inf,inf,inf,9,inf,inf,inf,inf;inf,inf,7,0,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,5,0,inf,inf,inf,1,inf,inf;inf,inf,inf,1,3,0,4,inf,inf,inf,inf;inf,inf,

13、inf,2,inf,inf,0,inf,3,1,inf;inf,inf,inf,inf,2,inf,inf,0,inf,inf,inf;inf,inf,inf,inf,inf,6,inf,7,0,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,1,0,1;inf,inf,inf,inf,inf,inf,inf,inf,2,inf,0%x=input（'输入邻接矩阵:'）;start=input（'输入起点：）；terminal=input（'输入终点：'）;fprintf（'计算结果如下：'）;D,path

14、,min,path_way=floyd（x,start,terminal）9湖南大学测试结果说明(l)Di.jistra 算法讦算最短路径(Di jkMg算法x -02IInfTnfInfInfInfInfInf20Inf61InfInf&InfInfInf1Inf07InfInf9InfInfInfInf060512InfInfInfInfInf1Inf503Inf21InfInfItrfInfInf1304Inf6InfInfIrrfInf92Inf40Inf31InfInfInfInfInf2InfInf01IiifMInfInfInfInfInf637012IrrfInfInf

15、IrrfInfInf1InfI1IrrfInfInfInfInfInfInfInf210输入起点：1输入绻点：11计算结果如下、min =6path_way =125911根据无向图A,可以知道matlab计算出来的结果是正确的(2)Floyd 算法计莒最疽路径任甬殉其法)Inf Inf Inf Inf Inf InfInf Inf Inflitnflit1rLfInfInfnfInfIInfInfInfnrrfnfn-fIrfn'fMnf I I I I I I I nfl'SMRfnfHnf I I I I I I LIrfIirfInfInfInfInfInfInE101InfInfInfInfInfInfInfInf2Inf0输入起点：1输入终点；11iriiri -16pathway -12596 T 10 H根据有