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

1、三、计算单源最短路问题（Dijkstra算法）,所谓单源是指一个出发顶点，单源最短路问题指的是该顶点至所有可达顶点的最短路径问题。 【例题】设计公共汽车线路(3) 现有一张县城的城镇地图，图中的顶点为城镇，无向边代表两个城镇间的连通关系，边上的权为公路造价，县城所在的城镇为v0。由于该县的经济比较落后，因此公路建设只能从县城开始规划。规划的要求是所有可达县城的城镇必须建设一条通往县城的汽车线路，该线路的工程的总造价必须最少。 输入： n (城市数，1n20) 县城所在的城镇序号v0 e (有向边数1e210) 以下e行，每行为3个整数，两个城镇的序号和它们间的公路造价 输出： k行，每行为一条

2、通往县城的汽车线路的总造价和该条线路途径的城镇序号,分析： 设G=（V，E）是一个有向图，它的每一条边（U，V）都有一个权W（U，V），在G中指定一个结点V0，要求把从V0到G的每一个结点Vj(V)的最短有向路找出来（或者指出不存在从V0到Vj的有向路，即V0不可达Vj）。这个问题即为单源最短路问题。解决单源最短路径的基本思想是把图中所有结点分为两组，每一个结点对应一个距离值 第一组：包括已确定最短路径的结点，结点对应的距离值是由v0到此结点的最短路径长度； 第二组：包括尚未确定最短路径的结点，结点对应的距离值是v0经由第一组结点（中间结点）至此结点的最短路径长度； 我们按最短路径长度递增的顺

3、序把第二组的结点加到第一组中去，直至v0可达的所有结点都包含于第一组。在这个过程中，总保持从v0到第一组各结点的最短路径长度都不大于从v0至第二组任何结点的路径长度。具体作法是： 初始时v0进入第一组，v0的距离值为0；第二组包含其它所有结点，这些结点对应的距离值这样确定（设vi为第二组中的结点） 然后每次从第二组的结点中选一个其距离值为最小的结点vm加到第一组中。每往第一组加入一个结点vm，就要对第二组的各结点的距离值作一次修正（设vi为第二组的结点）： 若加进vm做中间结点使得v0至vi的路径长度更短（即vi的距离值vm的距离值+Wmi），则要修改vi的距离（vi的距离值vm的距离值+Wm

4、i）。修改后再选距离值最小的一个结点加入到第一组中，。如此进行下去，直至第一组囊括图的所有结点或再无可加入第一组的结点存在。显然，这种从第二组的结点中选距离值最小的结点扩展是一种贪心策略。,设 n图的结点数； adj有向图的相邻矩阵。其中 dist最短路径集合。其中 distipre在v0至vi的最短路径上，vi的前趋结点序号； distilengthv0至vI的最短路径长度，即vi的距离值； （1in） Const n=图的结点数； Type path=record 路径集合的结点类型 length：real； 距离值 pre：0n； 前趋结点序号 end； var adj：array1n，

5、1n of real 相邻矩阵 dist：array1n of path； 路径集合,计算单源最短路径的过程如下： fillchar(adj，sizeof(adj)，0)；建立相邻矩阵adj for i1 to n do for j1 to n do if（i，j）E then adji，jwij else adji，j； for i1 to n do 路径集合初始化 begin distilengthadjv0，i； if distilength then distiprev0 else distipre0； end；for adjv0，v01；源结点v0进入第一组 repeat min；u

6、0； for i1 to n do 从第二组中找距离值最小的结点u,if (adji，i=0)and(distilength0 第二组中存在一个距离值最小的结点 then begin adju，u1；结点u进入第一组 for i1 to n do 修正第二组中u可达的结点距离值 if(adji，i=0)and(distilengthdistulength+adju，i) then begin distilengthdistulength+adju，i； distipreu； end；then end；then until u=0；,算法结束时，沿着结点vi的pre指针回溯，便可确定v0至vi的

7、最短路径： procedure print(i：integer)； begin if i=v0 then 输出结点v0 else begin print(distipre)； 输出结点i和v0至vi的最短路径长度distilength； end；else end；print 显然递归调用print1，printn后，可得知v0至所有结点的最短路径。由此得出主程序： 输入城镇数n； 输入出发城镇序号v0； 输入城镇间的距离矩阵w； 计算单源最短路径方案dist； for i1 to n do 枚举除v0外的其它城镇 begin if (iv0 )and(distilength)若城镇i与城镇v0

8、间有通路，则输出它们之间的最短距离和路径方案 then begin wrtiln(distilength)；print(i)；end；then wrteln； end；for,位图,给定一个n*m的矩形位图，位图中的每个像素不是白色就是黑色，但至少有一个是白色的。第i行、第j列的像素被称作像素(i， j)。两个像素p1 = (i1， j1)，p2 = (i2， j2)之间的距离定义为：d(p1， p2) = |i1 - i2| + |j1 - j2|。现在请你计算图中每个像素与离其最近的“白像素”的距离。 【输入】 输入文件BIT.IN的第一行包含两个整数n， m（1n150， 1m150），

9、用一个空格隔开。接下来n行，每一行都包含一个长度为m的01串；第i+1行，第j列的字符若为1，则像素(i， j)是白色的；否则是黑色的。 【输出】 文件BIT.OUT包含n行，每行有m个用空格隔开的整数。第i行、第j列的整数表示(i， j)与离它最近的白像素之间的距离。,算法分析,1.由于是求所有黑像素的点到白像素的最短距离，所以采用适合于整体计算floyd算法比较好，但floyd算法的时间复杂度为O（n3m3），不能满足时间要求。 2.考虑用求单源最短路径的算法：对于每一点进行一次宽度优先搜索，求该点到其他各点的最短距离。但这一算法的时间复杂度也达到了O（n2m2）， 3. 在前面的方法里，

10、我们是将每个黑像素到白像素的距离作为单独的问题来考虑的。这里忽略了一个重要的信息：相邻的黑像素之间有着很强的联系。定义：f（x，y）表示像素（x，y）到最近的白像素的距离。 f（x，y）=minf（x-1，y），f（x+1，y），f（x，y-1），f（x，y+1）+1 看到了这个式子，眼前顿时豁然开朗：前面所用的宽度优先搜索是以黑像素作为源点，得到的是单源最短路；而现在以白像素作为源点，求的是多源最短路。采用多源最短路径的算法求解本题，时间复杂度仅为O（n*m），时效大为改善。,设 const maxn=150；位图的规模 move：array1.4，1.2 of integer=(1，0)，

11、(0，1)，(-1，0)，(0，-1)；四个方向所对应的水平竖直增量 var used：array1.maxn，1.maxn of boolean；像素已访问标志 list：array1.maxn*maxn，1.2 of integer；listi为第i个源点(白像素)的坐标 map：array1.maxn，1.maxn of integer；mapi，j为（i，j）的像素离最近白像素的距离 i，j，n，p，q，x，y，t1，t2，m ：integer；n、m为bit图的规模，p，q为队列的首尾指针,readln(n，m)； 读bit图的规模 p：=1； q：=0； 队列的首尾指针初始化 fo

12、r i：=1 to n do begin 读入bit图，白像素作为源点入队 for j：=1 to m do begin read(ch)； if ch=1 then begin inc(q)；listq，1：=i；listq，2：=j； usedi，j：=true； mapi，j：=0； （i，j）的白像素已访问,离最近白像素的距离初始化 end；then end；for readln； end；for,while p=1) and (t2=1) and (not usedt1，t2) then begin 若该坐标在界内且未访问，则入队、设访问标志，并计算该像素离最近白像素的距离 inc(

13、q)；listq，1：=t1；listq，2：=t2；usedt1，t2：=true；mapt1，t2：=mapx，y+1； end；then end；for inc(p)； 出队 end；while for i：=1 to n do 输出每一个像素离最近白像素的距离 begin for j：=1 to m do write(mapi，j， )；writeln；end；for,例题：货币兑换,若干个货币兑换点在我们的城市中工作着。每个兑换点只能进行两种指定货币的兑换。不同兑换点兑换的货币有可能相同。每个兑换点有它自己的兑换汇率，货币A到货币B的汇率表示要多少单位的货币B才能兑换到一个单位的货币

14、A。当然货币兑换要支付一定量的中转费。例如，如果你想将100美元兑换成俄元，汇率是29.75，中转费为0.39，那么你会兑换到(100-0.39)29.75=2963.3975俄元。 城市中流通着N(N100)类货币，用数字1至N标号表示。每个货币兑换点用6个数字来描述：整数A和B是兑换货币的编号，实数RAB，CAB表示A兑换成B的汇率和中转费用，RBA，CBA表示B兑换成A的汇率和中转费用。 Nick有一些第S类货币，他想在若干次交换后增加他的资金，当然这些资金最终仍是第S类货币。请你告诉他该想法能否实现。,构图,将N种货币看成N个顶点，将每个兑换点转化为两条有向边。根据兑换公式，目前从A货币兑换到B货币的汇率和中转费用为RAB，CAB，那么由对应的A顶点向B顶点连一条有向边，从A点得到的B的可能最大值为： (A目前的最大值-CAB)RAB。 注意，这里所求的是最大值，为了转化为最短路，我们可以在数字前面加上一个负号。,1、利用求最短路的方法求最长路。由于存在负权（求最长路和负权等价），所以在这里Dijkstra算法不适用了，必须采用Bellman-Ford算法。 2、需要指出一点，无论是求负权最短路还是求最长路，可能遇到的一个问题是可能存在环，从而导致货