最短路问题及算法.doc

最短路问题及算法（上）
题：
求如图所示中从顶点到到其他顶点的最短路。
此处利用Dijkstra算法，其MATLAB的程序如下：

1

7
5
8
6
1
4
2
6
3
3
9
9
2

1

解法：
写出带权邻接矩阵：

Matlab的程序：
首先建立function文件：
function[l,z]=Dijkstra(W)
W=[0218InfInfInfInf;
20Inf61InfInfInf;
1Inf07InfInf9Inf;
8670512Inf;
Inf1Inf503Inf9;
InfInfInf13046;
InfInf92Inf403;
InfInfInfInf9630]
n=size(W,1);
fori=1:n
l(i)=W(1,i);
z(i)=1;
end
i=1;
whilei<=n
forj=1:n
ifl(i)>l(j)+W(j,i)
l(i)=l(j)+W(j,i);
z(i)=j;
ifj<i
i=j-1;
end
end
end
i=i+1;
end
l
z
结果：
l=021736912
z=11162545