文档介绍：最短路径问题
Mathematica Modeling
参考书：
龚劬 刘琼荪 何中市 《数学实验》科学出版社
李淑华 《数据结构教程C语言版》中国电力出版社
主讲：重庆大学 龚 格式为
[min,path]=dijkstra(w,start,terminal),
其中输入变量w为所求图的带权邻接矩阵，start, terminal分别为路径的起点和终点的号码。返回start到terminal的最短路径path及其长度min.
注意：顶点的编号从1开始连续编号。
9
最短路径算法
Floyd算法
使用范围:
求每对顶点的最短路径;
有向图、无向图和混合图;
算法思想:
直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D(1), D(2), …, D(n), D(n)是图的距离矩阵, 同时引入一个后继点矩阵记录两点间的最短路径.
10
2
3
7
4
11
6
5
9
8
1
3
5
12
2
10
6
1
5
8
8
7
9
9
3
2
2
7
10
Floyd算法——算法步骤
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),则
d(i,j)d(i,k)+d(k,j) , path(i,j)path(i,k) , k k+1
3）重复2)直到k=n+1
11
MATLAB程序（Floyd算法）
function [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(i,j)=j;
end, end, end
for 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, end,end
if nargin==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(i+1)=terminal;
path1=m;
end
12
最短路径算法
Floyd算法程序的使用说明：
1. [D, path]=floyd(a), 返回矩阵D, path 。其中a是所求图的带权邻接矩阵，D(i,j)表示i到j的最短距离; path(i,j)表示i与j之间的最短路径上顶点i的后继点.
2. [D, path, min1, path1]= floyd(a,i,j) 返回矩阵D, path; 并返回i与j之间的最短距离min1和最短路径path1.
13
edge= [ 2,3,1,3,3,5,4, 4,1,7,6,6,5, 5,11, 1,8,6,9,10,8,9, 9,10;...
3,4,2,7,5,3,5,11,7,6,7,5,6,11, 5, 8,1,9,5,11,9,8,10,9;...
3,5,8,5,6,6,1,12,7,9,9,2,2,10,10,8,8,3,7, 2, 9,9, 2, 2];
n=11; weight=inf*ones(n, n);
for i=1:n
weight(i, i)=0;
end
for i=1:size(edge,2)
weight(edge(1, i), edge(2, i))=edge(3, i);
end
[dis, path]=dij