文档介绍：最短路径问题
Mathematica Modeling
参考书:
《数学实验》科学出版社
《数据结构教程C语言版》中国电力出版社
主讲:重庆大学龚劬
1
主要内容
Floyd算法
Dijkstra算法
两个例子的求解
引例2:最廉价航费表的制定
引例1:最短运输路线问题
2
如图的交通网络,每条弧上的数字代表车辆在该路段行驶所需的时间,有向边表示单行道,无向边表示可双向行驶。若有一批货物要从1号顶点运往11号顶点,问运货车应沿哪条线路行驶,才能最快地到达目的地?
引例1:最短运输路线问题
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
3
某公司在六个城市C1,C2,C3,C4,C5,C6都有分公司,公司成员经常往来于它们之间,已知从Ci到Cj的直达航班票价由下述矩阵的第i行,第j列元素给出(表示无直达航班),该公司想算出一张任意两个城市之间的最廉价路线航费表。
引例2:最廉价航费表的制定
4
最短路径问题
定义:设P(u,v)是加权图G中从u到v的路径,则该路径上的边权之和称为该路径的权,记为w(P). 从u到v的路径中权最小者 P*(u,v)称为u到v的最短路径.
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
5
最短路径算法
Dijkstra算法
使用范围:
寻求从一固定顶点到其余各点的最短路径;
有向图、无向图和混合图;
权非负.
算法思路:
采用标号作业法,每次迭代产生一个永久标号, 从而生长一颗以v0为根的最短路树,在这颗树上每个顶点与根节点之间的路径皆为最短路径.
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
6
Dijkstra算法——算法步骤
S: 具有永久标号的顶点集;
l(v): v的标记; f(v):v的父顶点,用以确定最短路径;
输入加权图的带权邻接矩阵w=[w(vi,vj)]nxm.
初始化令l(v0)=0,S=; vv0 ,l(v)=;
更新l(v), f(v)
寻找不在S中的顶点u,使l(u),然后对所有不在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中为止.
7
MATLAB程序(Dijkstra算法)
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;
end, end
s(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=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;
while path(i)~=start
path(i+1)=f(path(i));
i=i+1 ;
end
path(i)=start;
L=length(path);
path=path(L:-1:1);
①
②
③
8
最短路径算法
Dijkstra算法程序的使用说明:
调用格式为
[min,path]=dijkstra(w,start,terminal),
其中输入变量w为所求图的带权邻接矩阵,start