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

三、计算单源最短路问题(Dijkstra 算法) 所谓单源是指一个出发顶点,单源最短路问题指的是该顶点至所有可达顶点的最短路径问题。【例题】设计公共汽车线路(3) 现有一张县城的城镇地图,图中的顶点为城镇,无向边代表两个城镇间的连通关系, 边上的权为公路造价,县城所在的城镇为 v 0。由于该县的经济比较落后,因此公路建设只能从县城开始规划。规划的要求是所有可达县城的城镇必须建设一条通往县城的汽车线路,该线路的工程的总造价必须最少。输入: n ( 城市数, 1≤n≤ 20) 县城所在的城镇序号 v 0 e ( 有向边数 1≤e≤ 210) 以下 e行,每行为 3个整数, 两个城镇的序号和它们间的公路造价输出: k行,每行为一条通往县城的汽车线路的总造价和该条线路途径的城镇序号分析: 设 G= (V,E) 是一个有向图,它的每一条边( U,V)∈ E都有一个权 W(U,V ),在 G 中指定一个结点 V 0, 要求把从V 0到G 的每一个结点 V j (V J∈V) 的最短有向路找出来(或者指出不存在从 V 0到V j 的有向路,即 V 0不可达 V j)。这个问题即为单源最短路问题。解决单源最短路径的基本思想是把图中所有结点分为两组,每一个结点对应一个距离值第一组:包括已确定最短路径的结点,结点对应的距离值是由 v 0到此结点的最短路径长度; 第二组:包括尚未确定最短路径的结点,结点对应的距离值是 v 0 经由第一组结点(中间结点)至此结点的最短路径长度; 我们按最短路径长度递增的顺序把第二组的结点加到第一组中去,直至 v 0 可达的所有结点都包含于第一组。在这个过程中,总保持从 v 0 到第一组各结点的最短路径长度都不大于从 v 0 至第二组任何结点的路径长度。具体作法是: 初始时 v 0 进入第一组, v 0 的距离值为 0 ;第二组包含其它所有结点,这些结点对应的距离值这样确定(设 v i为第二组中的结点) 然后每次从第二组的结点中选一个其距离值为最小的结点 v m 加到第一组中。每往第一组加入一个结点 v m,就要对第二组的各结点的距离值作一次修正(设 v i为第二组的结点): 若加进 v m做中间结点使得 v 0至v i的路径长度更短(即 v i的距离值>v m的距离值+W mi), 则要修改 v i的距离( v i的距离值←v m的距离值+W mi)。修改后再选距离值最小的一个结点加入到第一组中, …。如此进行下去,直至第一组囊括图的所有结点或再无可加入第一组的结点存在。显然,这种从第二组的结点中选距离值最小的结点扩展是一种贪心策略。???????Evv Evvw dist i iii),( ),( 0 00 设n—图的结点数; adj —有向图的相邻矩阵。其中 dist —最短路径集合。其中 dist[i] . pre —在v 0至v i的最短路径上, v i的前趋结点序号; dist[i] . length —v 0至v I的最短路径长度,即 v i的距离值; (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 ;{路径集合} 计算单源最短路径的过程如下: 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]←w ij else adj[i , j]←∞; for i ← 1 to n do { 路径集合初始化} begin dist[i] . length ← adj[v 0, i]; if dist[i] . length<> ∞ then dist[i] . pre ←v 0 else dist[i] . pre ←0; end ; {for} adj[v 0,v 0]←1;{源结点 v 0进入第一组} repeat min ←∞;u←0; for i ← 1 to n do { 从第二组中找距