郭辉各-Dijkstra算法.ppt

最短路经问题(Dijkstra算法) 核心思想：按路径递增的次序产生最短路径的算法 1)找到图中最短的路径，设为（v,vj）,将j设为已标号的点 2)找下一条次短的路径，假设终点为k,将k设为已标号的点,那么要么是（v,vk）要么是（v,vj,vk）,若经过vj ,将j设为已检查的点,放入集合. 3)以次短路径出发找第三短的路径,类似第二步的方法. 4)按上述方法一直到所有的顶点被检查过,则从v到其他顶点的最短路径求出. 典型例题:Transport Goods A国现在爆发了战争,现在急需从多个城市运输货物到首都去，在路上货物将有损耗率，当然损耗率是小于1的.一个城市只能运输它的货物到与之相连的另一个城市中去。你的任务在于找出最多能运输多少货物到首都去。【输入数据】： 首先给出N和M。其中2=N=100,它代表城市的个数，首都是第N个城市。M代表有多少条道路.接下来N-1行代表从第一个城市到第N-1城市这些城市本身有多少货物。这个值小于5000接下来M行代表城市相连的情况及损耗率 【输出数据】: 最多可以运输多少货物到首都去. 【样例输入】 5 6101010101 3 01 4 02 3 02 4 03 5 04 5 0 【样例输出】 40.00 【样例输入】 5 6101010101 3 01 4 02 3 02 4 03 5 04 5 0 【样例输出】 40.00 分析:这个题是按多个城市的货物运到首都去，因为我们可以用单源最短路径的算法，求出每个城市到首都的最短路径，由于从某个城市到首都可能经过多个点,货物的最终运输率,等于经过的边的运输率的乘积,因而这里的最短路径其实是求最大的货物有效运输效率。因此在读入数据的时候，将损耗率转成有效运输效率。 const MaxN = 100; var a : array[1..MaxN,1..MaxN] of double; w : array[1..MaxN] of integer; d : array[1..MaxN] of double; v : array[1..MaxN] of boolean; i,j,k,n,m : integer; max,r,ans : double; begin fillchar(a,sizeof(a),0); fillchar(w,sizeof(w),0); readln(n,m); for i := 1 to n - 1 do readln(w[i]); for i := 1 to m do begin readln(j,k,r); a[j,k] := 1 - r; a[k,j] := a[j,k]; end; fillchar(d,sizeof(d),0); fillchar(v,sizeof(v),0); for i := 1 to n - 1 do d[i] := a[i,n]; d[n] := 1; v[n] := true; for i := 1 to n - 1 do begin max := 0; k := 0; for j := 1 to n do if (not v[j]) and (d[j] max) then {找一个最大的有效运输率} begin max := d[j]; k := j; end; v[k] := true; for j := 1 to n do if (not v[j]) and (d[k] * a[k,j] d[j]) then d[j] := d[k] * a[k,j]; end; ans := 0; for i := 1 to n - 1 do ans := ans + w[i] * d[i]; writeln(ans : 0 : 2); end. 典型例题:最佳路线  　　塞内加尔是非洲的一个小国家，你也许很难在世界地图上找到它，甚至你有可能从未听说过它--它实在是个太小、太贫