最短路问题(Dijkstra算法).ppt

三、计算单源最短路问题(Dijkstra算法)
所谓单源是指一个出发顶点,单源最短路问题指的是该顶点至所有可达顶点的最短路径问题。
【例题】设计公共汽车线路(3)
现有一张县城的城镇地图,图中的顶点为城镇,无向边代表两个城镇间的连通关系,边上的权为公路造价,县城所在的城镇为v0。由于该县的经济比较落后,因此公路建设只能从县城开始规划。规划的要求是所有可达县城的城镇必须建设一条通往县城的汽车线路,该线路的工程的总造价必须最少。
输入:
n (城市数,1≤n≤20)
县城所在的城镇序号v0
e (有向边数1≤e≤210)
以下e行,每行为3个整数,两个城镇的序号和它们间的公路造价
输出:
k行,每行为一条通往县城的汽车线路的总造价和该条线路途径的城镇序号
设菊境卖经顽谢菠蜡抚让易抒焉及颓尸拳闭绑醋时薄琳出房礼趾与赃荆撇最短路问题(Dijkstra算法)最短路问题(Dijkstra算法)
分析:
设G=(V,E)是一个有向图,它的每一条边(U,V)∈E都有一个权W(U,V),在G中指定一个结点V0,要求把从V0到G的每一个结点Vj(VJ∈V)的最短有向路找出来(或者指出不存在从V0到Vj的有向路,即V0不可达Vj)。这个问题即为单源最短路问题。解决单源最短路径的基本思想是把图中所有结点分为两组,每一个结点对应一个距离值
第一组:包括已确定最短路径的结点,结点对应的距离值是由v0到此结点的最短路径长度;
第二组:包括尚未确定最短路径的结点,结点对应的距离值是v0经由第一组结点(中间结点)至此结点的最短路径长度;
我们按最短路径长度递增的顺序把第二组的结点加到第一组中去,直至v0可达的所有结点都包含于第一组。在这个过程中,总保持从v0到第一组各结点的最短路径长度都不大于从v0至第二组任何结点的路径长度。具体作法是:
初始时v0进入第一组,v0的距离值为0;第二组包含其它所有结点,这些结点对应的距离值这样确定(设vi为第二组中的结点)

然后每次从第二组的结点中选一个其距离值为最小的结点vm加到第一组中。每往第一组加入一个结点vm,就要对第二组的各结点的距离值作一次修正(设vi为第二组的结点):
若加进vm做中间结点使得v0至vi的路径长度更短(即vi的距离值>vm的距离值+Wmi),则要修改vi的距离(vi的距离值←vm的距离值+Wmi)。修改后再选距离值最小的一个结点加入到第一组中,…。如此进行下去,直至第一组囊括图的所有结点或再无可加入第一组的结点存在。显然,这种从第二组的结点中选距离值最小的结点扩展是一种贪心策略。
览翅所膀道眨题呸汉角制绊独狗世末疤毋澡赢钥锭赠撇狗廓税羹胶帕髓疙最短路问题(Dijkstra算法)最短路问题(Dijkstra算法)
设
n—图的结点数;
adj—有向图的相邻矩阵。其中
dist—最短路径集合。其中
dist[i].pre—在v0至vi的最短路径上,vi的前趋结点序号;
dist[i].length—v0至vI的最短路径长度,即vi的距离值;
(1≤i≤n)
Const n=图的结点数;
Type
path=record {路径集合的结点类型}
length:real; {距离值}
pre:0‥n; {前趋结点序号}
end;
var
adj:array[1‥n,1‥n] of real {相邻矩阵}
dist:array[1‥n] of path; {路径集合}
疡***燥拖砍妮锅缘桅着掌礼归哭褂颅疵攻站喝啮涛手纹揪戚坞由涟篆漏吼最短路问题(Dijkstra算法)最短路问题(Dijkstra算法)
计算单源最短路径的过程如下:
fillchar(adj,sizeof(adj),0);{建立相邻矩阵adj}
for i←1 to n do
for j←1 to n do
if(i,j)∈E then adj[i,j]←wij
else adj[i,j]←∞;
for i←1 to n do {路径集合初始化}
begin
dist[i].length←adj[v0,i];
if dist[i].length<>∞
then dist[i].pre←v0
else dist[i].pre←0;
end;{for}
adj[v0,v0]←1;{源结点v0进入第一组}
repeat
min←∞;u←0;
for i←1 to n do {从第二组中找距离值最小的结点u}
if (adj[i,i]=0)and(dist[i].length<min)
then begin u←i;min←dist[i].length;end;{then}
if u<>0 {第二组中存在一个距离值最小的结点}
then begin