最短路问题课件

赋权图给定赋权图的一个子图H，定义H的权为H的所有边权的总和。最短路问题对图G的每条边e，赋予一实数ω(e)，称为边e的权，可得一赋权图。UDBVCEA7122447315551赋权图给定赋权图的一个子图H，定义H的权为H的所有边权的总和赋权图中一条路的权称为路长。在一个赋权图G上，给定两个顶点u和v，所谓u和

v最短路是指所有连接顶点u和v

的路中路长最短的路；u和v最短路的路长也称为u和v的距离。UDBVCEA2274147315552赋权图中一条路的权称为路长。在一个赋权图G上，给定两个顶点uDijkstra算法的基本思想：(1)u0u1P设S是V的真子集，如果是从u

0到的最短路，则，并且P的段是最短的路，所以3Dijkstra算法的基本思想：(1)u0u1P设S是V的真算法标号令lij表示从顶点vi到顶点vj的距离；dij表示连接顶点vi与顶点vj边上的权，即公式（1）是Dijkstra算法的基础。算法以标号方式进行，每进行一次都增加一个标号点，直至找到所求的最短路。(1)4算法标号令lij表示从顶点vi到顶点vj的距离；dij表Dijkstra算法步骤Step0在点vs上标号lss=0；Step4lst是所求的最短路长，反向追踪找出所求vs-vt最短路.Step3令Step2令S表示所有已标号点，表示未标号点，计算lsj

，转Step3Step1若vt已标号，转Step4；否则转Step2；5Dijkstra算法步骤Step0在点vs上标号lss=计算实例求连接S、V的最短路SDBVCEA2274147315556计算实例求连接S、V的最短路SDBVCEA227414731SDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s7SDBVCEA22741473155502，s5，s4，s∞SDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s9，A4，A4，s8SDBVCEA22741473155502，s5，s4，s∞SDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s9，A4，A4，s8，C4，A9SDBVCEA22741473155502，s5，s4，s∞SDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s9，A4，A4，s8，C4，A7，B7，B10SDBVCEA22741473155502，s5，s4，s∞SDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E11SDBVCEA22741473155502，s5，s4，s∞SDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E13，D13，D12SDBVCEA22741473155502，s5，s4，s∞LUV

=13;S-V最短路为SABEDVSDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E13，D13，D13LUV=13;S-V最短路为SABEDVSDBVCEA2实例评述Dijkstra算法不仅找到了所求最短路，而且找到了从S点到其他所有顶点的最短路；这些最短路构成了图的一个连通无圈的支撑子图，即图的一个支撑树。SDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E13，D13，D14实例评述Dijkstra算法不仅找到了所求最短路，而且找到了Dijkstra算法也适用于有向赋权图.SDBVCEA71224473155515Dijkstra算法也适用于有向赋权图.SDBVCEA712选址问题设G表示一个矿区的交通运输图，矿井和之间的里程是；现在需建一个矿区煤炭运输站，把运输站设在哪个矿井所在地才能使得离运输站距离最远的矿井可运输里程最短。这就是最简单的选址问题。矿区的交通运输图是一个赋权图，每个矿井是图的一个顶点。在赋权图G中，定义顶点u的离距为：16选址问题设G表示一个矿区的交通运输图，矿井和之间的里程是中心问题网络G的一个中心是满足下列条件的G的顶点u选址问题可化为求G的中心问题。求图的中心的算法过程：用Dijkstra算法求出G的任意两点间的距离；求出每点的离距d(v)求满足（2）的顶点v即是中心（2）17中心问题网络G的一个中心是满足下列条件的G的顶点u（2）17实例图7-15给出了一个矿区的交通运输图。应把运输站建在哪个矿井才能满足选址要求？v3v4v5v2v6v1v763221.531.81.52.518实例图7-15给出了一个矿区的交通运输图。应把运输站建在哪个这个问题实际上只需求出G的一个中心即可。按上面的算法过程，首先利用Dijkstra算法得到图7-15的距离表；再求出每个点的离距，最后找出离距的最小者v6就是建运输站的矿井。4.8v*=19这个问题实际上只需求出G的一个中心即可。按上面的算法过程，首注:Dijkstra算法只适用于所有ｗij≥0的情形，当赋权有向图中存在负权时，算法失效。如v1v2v312-3用Dijkstra算法可以得出从ｖ1到v2的最短路的权是1，但实际上从ｖ1到v2的最短路是（ｖ1，v3

，v2），权是-1。20注:Dijkstra算法只适用于所有ｗij≥0的情形，当赋权下面介绍具有负权赋权有向图D的最短路的算法。不妨假设从任一点vi到任一点vj都有一条弧（如果在D中，（vi，vj

）A，则添加弧（vi，vj

）令wij=+∞）。显然，从vs到任一点vj的最短路总是从vs出发到某个点vi，再沿（vi，vj）到vj的，由前面的结论可知，从vs到vi的这条路必定是从vs到vi的最短路，所以d（vs，vj）必满足如下方程：21下面介绍具有负权赋权有向图D的最短路的算法。不妨假设从任一点22226-1-3-283-52-111-1217-3-5例：求ｖ1到各点的最短路236-1-3-283-52-111-1217-3-5例：求ｖ1wijv1v2v3v4v5v6v7v8t=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-506624-24赋权图给定赋权图的一个子图H，定义H的权为H的所有边权的总和。最短路问题对图G的每条边e，赋予一实数ω(e)，称为边e的权，可得一赋权图。UDBVCEA71224473155525赋权图给定赋权图的一个子图H，定义H的权为H的所有边权的总和赋权图中一条路的权称为路长。在一个赋权图G上，给定两个顶点u和v，所谓u和

v最短路是指所有连接顶点u和v

的路中路长最短的路；u和v最短路的路长也称为u和v的距离。UDBVCEA22741473155526赋权图中一条路的权称为路长。在一个赋权图G上，给定两个顶点uDijkstra算法的基本思想：(1)u0u1P设S是V的真子集，如果是从u

0到的最短路，则，并且P的段是最短的路，所以27Dijkstra算法的基本思想：(1)u0u1P设S是V的真算法标号令lij表示从顶点vi到顶点vj的距离；dij表示连接顶点vi与顶点vj边上的权，即公式（1）是Dijkstra算法的基础。算法以标号方式进行，每进行一次都增加一个标号点，直至找到所求的最短路。(1)28算法标号令lij表示从顶点vi到顶点vj的距离；dij表Dijkstra算法步骤Step0在点vs上标号lss=0；Step4lst是所求的最短路长，反向追踪找出所求vs-vt最短路.Step3令Step2令S表示所有已标号点，表示未标号点，计算lsj

，转Step3Step1若vt已标号，转Step4；否则转Step2；29Dijkstra算法步骤Step0在点vs上标号lss=计算实例求连接S、V的最短路SDBVCEA22741473155530计算实例求连接S、V的最短路SDBVCEA227414731SDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s31SDBVCEA22741473155502，s5，s4，s∞SDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s9，A4，A4，s32SDBVCEA22741473155502，s5，s4，s∞SDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s9，A4，A4，s8，C4，A33SDBVCEA22741473155502，s5，s4，s∞SDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s9，A4，A4，s8，C4，A7，B7，B34SDBVCEA22741473155502，s5，s4，s∞SDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E35SDBVCEA22741473155502，s5，s4，s∞SDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E13，D13，D36SDBVCEA22741473155502，s5，s4，s∞LUV

=13;S-V最短路为SABEDVSDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E13，D13，D37LUV=13;S-V最短路为SABEDVSDBVCEA2实例评述Dijkstra算法不仅找到了所求最短路，而且找到了从S点到其他所有顶点的最短路；这些最短路构成了图的一个连通无圈的支撑子图，即图的一个支撑树。SDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E13，D13，D38实例评述Dijkstra算法不仅找到了所求最短路，而且找到了Dijkstra算法也适用于有向赋权图.SDBVCEA71224473155539Dijkstra算法也适用于有向赋权图.SDBVCEA712选址问题设G表示一个矿区的交通运输图，矿井和之间的里程是；现在需建一个矿区煤炭运输站，把运输站设在哪个矿井所在地才能使得离运输站距离最远的矿井可运输里程最短。这就是最简单的选址问题。矿区的交通运输图是一个赋权图，每个矿井是图的一个顶点。在赋权图G中，定义顶点u的离距为：40选址问题设G表示一个矿区的交通运输图，矿井和之间的里程是中心问题网络G的一个中心是满足下列条件的G的顶点u选址问题可化为求G的中心问题。求图的中心的算法过程：用Dijkstra算法求出G的任意两点间的距离；求出每点的离距d(v)求满足（2）的顶点v即是中心（2）41中心问题网络G的一个中心是满足下列条件的G的顶点u（2）17实例图7-15给出了一个矿区的交通运输图。应把运输站建在哪个矿井才能满足选址要求？v3v4v5v2v6v1v763221.531.81.52.542实例图7-15给出了一个矿区的交通运输图。应把运输站建在哪个这个问题实际上只需求出G的一个中心即可。按上面的算法过程，首先利用Dijkstra算法得到图7-15的距离表；再求出每个点的离距，最后找出离距的最小者v6就是建运输站的矿井。4.8v*=43这个问题实际上只需求出G的一个中心即可。按上面的算法过程，首注:Dijkstra算