matlab最短路径算法

最短路径问题

主要内容例：最短运输路线问题

Dijkstra算法

例子的求解

例：最短运输路线问题如图的交通网络，每条弧上的数字代表车辆在该路段行 驶所需的时间，有向边表示单行道，无向边表示可双向 行驶。若有一批货物要从 1号顶点运往 11号顶点，问运 货车应沿哪条线路行驶，才能最快地到达目的地？

2

3 5

36

5 6

4

8 1 7 7 88

1

12

99

23

5 10 11

9

7 2 10

23

最短路径问题 定义：设P(u,v)是加权图G中从u到v的路径,则该路

径上的边权之和称为该路径的权,记为w(P). 从u到v 的路径中权最小者 P*(u,v)称为u到v的最短路径. 2

3

3

5

4

8 1 7 7 88

596

62 39

1

12

5 10 11

9

7 2 10

24

最短路径算法Dijkstra算法使用范围:1) 2) 3)

2

3

3

8 1 7 7 88

5 2 6 9 3 7 9 9 2

5 4 6 1

10

1 5 12 11 0 2

寻求从一固定顶点到其余各点的最短路径; 有向图、无向图和混合图; 权非负.

算法思路：采用标号作业法,每次迭代产生一个永久标号, 从而生长一颗以v0为根的最短路树,在这颗树上每

个顶点与根节点之间的路径皆为最短路径.

Dijkstra算法——算法步骤S: 具有永久标号的顶点集; l(v): v的标记; f(v):v的父顶点,用以确定最短路径; 输入加权图的带权邻接矩阵w=[w(vi,vj)]nxm.

初始化

令l(v0)=0,S= ; v v0 ,l(v)= ;

更新l(v), 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;

重复步骤2), 直到所有顶点都在S中为止.

MATLAB程序(Dijkstra算法)function [min,path]=dijkstra(w,start,terminal) n=size(w,1); label(start)=0; f(start)=start; for i=1:n min=label(terminal); if i~=start path(1)=terminal; label(i)=inf; i=1; end, end s(1)=start; u=start; while path(i)~=start path(i+1)=f(path(i)); while length(s)<n i=i+1 ; for i=1:n ③ end ins=0; ① for j=1:length(s) path(i)=start; L=length(path); if i==s(j) path=path(L:-1:1); ins=1; end, end if ins==0 v=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

最短路径算法Dijkstra算法程序的使用说明：调用格式为

[min,path]=dijkstra(w,start,terminal),其中输入变量w为所求图的带权邻接矩阵，start, terminal分别为路径的起点和终点的号码。返回start 到terminal的最短路径path及其长度min. 注意：顶点的编号从1开始连续编号。

引例的Matlab求解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; e

nd for i=1:size(edge,2) end 2 8 1 7 7 8

35 9 9

3 6 2

56

4 1 5

12 10 11 2

39

8 weight(edge(1, i), edge(2, i))=edge(3, i);

7 2 10

[dis, path]=dijkstra(weight, 1, 11)9

引例的求解运行上页程序输出： dis = 21 path = 1 8 9 10 11

因此顶点1到顶点11的最短路径为1→8 →9 →10 →11, 其长度为21。