matlab计算最短路径

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

2、B，使用Warshall-Floyd算法思路及代码(1)思路（1）Dijkstra算法使用范围:1) 寻求从一固定顶点到其余各点的最短路径;2) 有向图、无向图和混合图;3) 权非负.算法思路： 采用标号作业法,每次迭代产生一个永久标号, 从而生长一颗以v0为根的最短路树,在这颗树上每个顶点与根节点之间的路径皆为最短路径.诉法步骤：S: 具有永久标号的顶点集;l(v): v的标记; f(v):v的父顶点,用以确定最短路径; 输入加权图的带权邻接矩阵w=w(vi,vj)nxm.1) 初始化 令l(v0)=0,S=F;" v¹v0 ,l(v)=¥2) 更新l(v),

3、f(v) 寻找不在S中的顶点u,使l(u)为最小.把u加入到S中,然后对所有不在S中的顶点v,如l(v)>l(u)+w(u,v),则更新l(v),f(v), 即 l(v)¬l(u)+w(u,v),f(v)¬u;3) 重复步骤2), 直到所有顶点都在S中为止.（2）Floyd算法使用范围:1) 求每对顶点的最短路径;2) 有向图、无向图和混合图;算法思想: 直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D(1), D(2), , D(n), D(n)是图的距离矩阵, 同时引入一个后继点矩阵记录两点间的最短路径.算法步骤：d(i,j) : i到j的距离;

4、 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),则 d(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算法)%min表示最短的距离%path表示最短路径%w表示

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

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

7、hile path(i)=start path(i+1)=f(path(i); i=i+1 ;end path(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,i

8、nf,inf,inf;inf,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('输入起

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

10、,j, D(i,j)<-a(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:n for j=1:n if D(i,j)=inf path

11、(i,j)=j; end endendfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)<D(i,j) D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k); end end endendif nargin=3%参数个数为3的时候执行 min1=D(start,terminal);%最短距离 m(1)=start; i=1; path1= ; %计算最短路径 while path(m(i),terminal)=terminal k=i+1; m(k)=path(m(i),terminal); i=i+1; end m

12、(i+1)=terminal; path1=m;end text02.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,

13、3,0,4,inf,inf,inf,inf;inf,inf,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,min,path_way=floyd(x,start,terminal)测试结果说明(1)Di.jistra算法根据无向图A，可以知道matlab计算出来的结果是正确的(2)Floyd算法根据有向图B，可以知道matlab计算出来的结果是正确