最短路问题课件.ppt

《最短路问题课件.ppt》由会员分享，可在线阅读，更多相关《最短路问题课件.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于最短路问题1第1页，此课件共24页哦v赋权图中一条路的权称为路长。赋权图中一条路的权称为路长。v在一个赋权图在一个赋权图G上，给定两个顶点上，给定两个顶点u和和 v，所谓，所谓u和和 v最短最短 路是指所有连接顶点路是指所有连接顶点u和和 v 的路中路长最短的路；的路中路长最短的路；vu和和 v最短路的路长也称为最短路的路长也称为u和和 v的距离。的距离。UDBVCEA227414731555第2页，此课件共24页哦vDijkstra算法的基本思想：算法的基本思想：(1)u0u1P设设S是是V的真子集，的真子集，如果是从如果是从u 0 到到 的最短路，的最短路，则则，并且，并且P的的 段是

2、最短的段是最短的路，所以路，所以第3页，此课件共24页哦算法标号算法标号v令令l ij表示从顶点表示从顶点vi到顶点到顶点vj的距离；的距离；dij表示连接顶点表示连接顶点vi与与顶点顶点vj边上的权，即边上的权，即公式（公式（1）是）是Dijkstra算法的基础。算法的基础。算法以标号方式进行，每进行一次都增加一个标号点，直至找到算法以标号方式进行，每进行一次都增加一个标号点，直至找到所求的最短路。所求的最短路。(1)第4页，此课件共24页哦Dijkstra算法步骤算法步骤vStep0 在点在点vs上标号上标号lss=0；vStep4 lst是所求的最短路长，反向追踪找出所是所求的最短路长，

3、反向追踪找出所求求vs-vt最短路最短路.vStep3 令令vStep2 令令S表示所有已标号点，表示所有已标号点，表示未标号点，表示未标号点，计算计算lsj，转，转Step3vStep1 若若vt已标号，转已标号，转Step4；否则转否则转Step2；第5页，此课件共24页哦计算实例计算实例求连接求连接S、V的最短路的最短路SDBVCEA227414731555第6页，此课件共24页哦SDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s第7页，此课件共24页哦SDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s

4、第8页，此课件共24页哦SDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，A第9页，此课件共24页哦SDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，A7，B7，B第10页，此课件共24页哦SDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E第11页，此课件共24页哦SDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，A

5、7，B7，B8，E14，E8，E13，D13，D第12页，此课件共24页哦LUV=13;S-V最短路为最短路为SABEDVSDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E13，D13，D第13页，此课件共24页哦实例评述实例评述vDijkstra算法不仅找到了所求最短路，而且找到了从算法不仅找到了所求最短路，而且找到了从S点到点到其他所有顶点的最短路；这些最短路构成了图的一个连其他所有顶点的最短路；这些最短路构成了图的一个连通无圈的支撑子图，即图的一个支撑树。通无圈的支撑子图，即图的一个支撑树。S

6、DBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E13，D13，D第14页，此课件共24页哦vDijkstra算法也适用于有向赋权图算法也适用于有向赋权图.SDBVCEA712244731555第15页，此课件共24页哦选址问题选址问题v设设G表示一个矿区的交通运输图，矿井和之间的里程是；现在表示一个矿区的交通运输图，矿井和之间的里程是；现在需建一个矿区煤炭运输站，把运输站设在哪个矿井所在地才能使得需建一个矿区煤炭运输站，把运输站设在哪个矿井所在地才能使得离运输站距离最远的矿井可运输里程最短。这就是最

7、简单的选址问离运输站距离最远的矿井可运输里程最短。这就是最简单的选址问题。题。v矿区的交通运输图是一个赋权图，每个矿井是图的一个顶点。矿区的交通运输图是一个赋权图，每个矿井是图的一个顶点。v在赋权图在赋权图G中，定义顶点中，定义顶点u的离距为：的离距为：第16页，此课件共24页哦中心问题中心问题网络网络G的一个中心是满足下列条件的的一个中心是满足下列条件的G的顶点的顶点u选址问题可化为求选址问题可化为求G的中心问题。的中心问题。求图的中心的算法过程：求图的中心的算法过程：用用Dijkstra算法求出算法求出G的任意两点间的距离；的任意两点间的距离；求出每点的离距求出每点的离距d(v)求满足（求

8、满足（2）的顶点）的顶点v即是中心即是中心（2）第17页，此课件共24页哦实例实例图图7-15给出了一个矿区的交通运输图。应把运输站建在给出了一个矿区的交通运输图。应把运输站建在哪个矿井才能满足选址要求？哪个矿井才能满足选址要求？v3v4v5v2v6v1v763221.531.81.52.5第18页，此课件共24页哦v这个问题实际上只需求出这个问题实际上只需求出G的一个中心即可。按上面的算法过的一个中心即可。按上面的算法过程，首先利用程，首先利用Dijkstra算法得到图算法得到图7-15的距离表；再求出每个的距离表；再求出每个点的离距，最后找出离距的最小者点的离距，最后找出离距的最小者v 6

9、就是建运输站的矿井。就是建运输站的矿井。4.8v*=第19页，此课件共24页哦注注:Dijkstra算法只适用于所有算法只适用于所有ij0的情形，当赋权有向的情形，当赋权有向图中存在负权时，算法失效。如图中存在负权时，算法失效。如v1v2v3 12-3用用Dijkstra算法可以得出从算法可以得出从1到到v2的最短路的权是的最短路的权是1，但实际上从，但实际上从1到到v2的最短路是（的最短路是（1，v3，v2），权是），权是-1。第20页，此课件共24页哦下面介绍具有负权赋权有向图下面介绍具有负权赋权有向图D的最短路的算法。的最短路的算法。不妨假设从任一点不妨假设从任一点vi到任一点到任一点v

10、j都有一条弧（如果在都有一条弧（如果在D中，（中，（vi，vj）A，则添加弧（，则添加弧（vi，vj）令）令wij=+）。）。显然，从显然，从vs到任一点到任一点vj的最短路总是从的最短路总是从vs出发到某个点出发到某个点vi，再，再沿（沿（vi，vj）到）到vj的，由前面的结论可知，从的，由前面的结论可知，从vs到到vi的这条路的这条路必定是从必定是从vs到到vi的最短路，所以的最短路，所以d（vs，vj）必满足如下方程：）必满足如下方程：第21页，此课件共24页哦第22页，此课件共24页哦6-1-3-283-52-111-1217-3-5例：求例：求1到各点的最短路到各点的最短路第23页，此课件共24页哦2022/10/5感谢大家观看第24页，此课件共24页哦