最短路问题课件.ppt

1、赋权图赋权图v给定赋权图的一个子图给定赋权图的一个子图H，定义，定义H的权为的权为H的所有边权的总和。的所有边权的总和。最短路问题最短路问题n对图对图G的每条边的每条边e，赋予一实数，赋予一实数(e)，称为边，称为边e的权，可得一的权，可得一赋权图。赋权图。UDBVCEA7122447315551v赋权图中一条路的权称为路长。赋权图中一条路的权称为路长。n在一个赋权图在一个赋权图G上，给定两个顶点上，给定两个顶点u和和 v，所谓，所谓u和和 v最短最短 路是指所有连接顶点路是指所有连接顶点u和和 v 的路中路长最短的路；的路中路长最短的路；nu和和 v最短路的路长也称为最短路的路长也称为u和和

2、 v的距离。的距离。UDBVCEA2274147315552vDijkstra算法的基本思想：算法的基本思想：),(),(),(00vuwuuduud,),(),(min),(00SvSuvuwuudSud(1)uvu0u1SPPSVSSu,0设设S是是V的真子集，的真子集，vuuP0S如果是从如果是从u 0 到到 的最短路，的最短路，Su),(0uu),(0uu则则，并且，并且P的的 段是最短的段是最短的路，所以路，所以3算法标号算法标号v令令l ij表示从顶点表示从顶点vi到顶点到顶点vj的距离；的距离；dij表示连接顶点表示连接顶点vi与顶点与顶点vj边上的权，即边上的权，即)(,)(,

3、GEvvGEvvwdjijiijij公式（公式（1）是）是Dijkstra算法的基础。算法的基础。算法以标号方式进行，每进行一次都增加一个标号点，算法以标号方式进行，每进行一次都增加一个标号点，直至找到所求的最短路。直至找到所求的最短路。,),(),(min),(00SvSuvuwuudSud(1)4Dijkstra算法步骤算法步骤vStep0 在点在点vs上标号上标号lss=0；,minSvSvdlljiijsisk,kkvSSvSSnStep4 lst是所求的最短路长，反向追踪找出是所求的最短路长，反向追踪找出所求所求vs-vt最短路最短路.nStep3 令令SnStep2 令令S表示所有

4、已标号点，表示所有已标号点，表示未标号点，表示未标号点，计算计算lsj，转，转Step3nStep1 若若vt已标号，转已标号，转Step4；否则转否则转Step2；5计算实例计算实例求连接求连接S、V的最短路的最短路SDBVCEA2274147315556SDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s7SDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8SDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，A9SDBVCEA22741473155

5、502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，A7，B7，B10SDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E11SDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E13，D13，D12LUV=13;S-V最短路为最短路为SABEDVSDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8

6、，E13，D13，D13实例评述实例评述vDijkstra算法不仅找到了所求最短路，而且找到了从算法不仅找到了所求最短路，而且找到了从S点到其他所有顶点的最短路；这些最短路构成了图的点到其他所有顶点的最短路；这些最短路构成了图的一个连通无圈的支撑子图，即图的一个支撑树。一个连通无圈的支撑子图，即图的一个支撑树。SDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E13，D13，D14vDijkstra算法也适用于有向赋权图算法也适用于有向赋权图.SDBVCEA71224473155515选址问题选址问题

7、v设设G表示一个矿区的交通运输图，矿井和之间的里程是；表示一个矿区的交通运输图，矿井和之间的里程是；现在需建一个矿区煤炭运输站，把运输站设在哪个矿井所在地现在需建一个矿区煤炭运输站，把运输站设在哪个矿井所在地才能使得离运输站距离最远的矿井可运输里程最短。这就是最才能使得离运输站距离最远的矿井可运输里程最短。这就是最简单的选址问题。简单的选址问题。v矿区的交通运输图是一个赋权图，每个矿井是图的一个顶点。矿区的交通运输图是一个赋权图，每个矿井是图的一个顶点。v在赋权图在赋权图G中，定义顶点中，定义顶点u的离距为：的离距为：ivjvijc),(max)(uVvvudud16中心问题中心问题网络网络G

8、的一个中心是满足下列条件的的一个中心是满足下列条件的G的顶点的顶点u选址问题可化为求选址问题可化为求G的中心问题。的中心问题。求图的中心的算法过程：求图的中心的算法过程：用用Dijkstra算法求出算法求出G的任意两点间的距离；的任意两点间的距离；求出每点的离距求出每点的离距d(v)求满足（求满足（2）的顶点）的顶点v即是中心即是中心),(min)(Vvvdud（2）17实例实例图图7-15给出了一个矿区的交通运输图。应把运输站建给出了一个矿区的交通运输图。应把运输站建在哪个矿井才能满足选址要求？在哪个矿井才能满足选址要求？v3v4v5v2v6v1v763221.531.81.52.518v这

9、个问题实际上只需求出这个问题实际上只需求出G的一个中心即可。按上面的算的一个中心即可。按上面的算法过程，首先利用法过程，首先利用Dijkstra算法得到图算法得到图7-15的距离表；再的距离表；再求出每个点的离距，最后找出离距的最小者求出每个点的离距，最后找出离距的最小者v 6就是建运就是建运输站的矿井。输站的矿井。3.605.13.63.34368.45.108.48.15.25.15.43.63.38.13023.63.93.63.38.13023.33.6545.2520253.635.13.63.32033.965.43.93.6530)(76543217654321vvvvvvvvd

10、vvvvvvvi4.8v*=19注注:Dijkstra算法只适用于所有算法只适用于所有ij0的情形，当赋的情形，当赋权有向图中存在负权时，算法失效。如权有向图中存在负权时，算法失效。如v1v2v3 12-3用用Dijkstra算法可以得出从算法可以得出从1到到v2的最短路的权是的最短路的权是1，但实际，但实际上从上从1到到v2的最短路是（的最短路是（1，v3，v2），权是），权是-1。20下面介绍具有负权赋权有向图下面介绍具有负权赋权有向图D的最短路的算法。的最短路的算法。不妨假设从任一点不妨假设从任一点vi到任一点到任一点vj都有一条弧（如果在都有一条弧（如果在D中，中，（vi，vj）A，则

11、添加弧（，则添加弧（vi，vj）令）令wij=+）。）。显然，从显然，从vs到任一点到任一点vj的最短路总是从的最短路总是从vs出发到某个点出发到某个点vi，再沿（再沿（vi，vj）到）到vj的，由前面的结论可知，从的，由前面的结论可知，从vs到到vi的的这条路必定是从这条路必定是从vs到到vi的最短路，所以的最短路，所以d（vs，vj）必满）必满足如下方程：足如下方程：ijisijswvvdvvd),(),(min21ijisijswvvdvvd),(),(min可用如下递推公式：为了求得这个方程的解),(,),(),(21nsssvvdvvdvvd），（令）（njwvvdsjjs21),(

12、1),2,1(),(),(321minnjwvvdvvdtijistijst）（）（，对有，步时，对所有第若进行到某一步，例如njk21),(),(1jskjskvvdvvd）（）（到各点的最短路的权。）既为，（则）（sjskvnjvvd21),(221v2v3v4v5v6v7v8v6-1-3-283-52-111-1217-3-5例：求例：求1到各点的最短路到各点的最短路23wijv1v2v3v4v5v6v7v8t=1t=2t=3t=4v10-1-230000v2602-1-5-5-5v3-30-51-2-2-2-2v4023-7-7-7v5-101-3-3v610-17-1-1-1v7-1-305-5-5v8-5066),(1jtvvd）（),2,1(),(),(321minnjwvvdvvdtijistijst）（）（，对24