最短路问题(课堂PPT).ppt

最短路问题*最短路径问题的实例搬家公司的最短路径安排 某搬家公司负责一户人家的搬家业务，从出发点V1到新居V7之间的各段路径距离如下图所示（单位：km）。请问搬家公司如何安排路径，使运输距离最短？ V3V2V4V5V6V1V7515537464876赋权有向图2*求解算法--Dijkstra算法基本原理：最短路的子路也是最短路。V2V3V429844V1易知v1到v4的最短路径为v1-v2-v3-v4，最短距离10则v1到v3的最短路径肯定为v1-v2-v3同样v1到v2的最短路肯定为v1-v2*实例的Dijkstra算法求解步骤(1)从起点v1出发，易知v1到v1的最短距离L11=0，对v1标号0V3V2V4V5V6V1V751553746487620*(2)找出同v1相邻的未标号的点有v2,v3,v4，求出从v1到其所有相邻点的距离(v1-v2:5;v1-v3:4;v1-v4:7)，距离最短路径为v1-v3，最短距离为L13=4，将v3标记为4V3V2V4V5V6V1V7515537464876204*(3)找出所有与v1,v3相邻的未标记的点v2,v4,v5，求出从v1直接到这些点的距离(v1-v2:5;v1-v4:7)以及经过v3到这些点的距离(v1-v3-v4:6;v1-v3-v5:12;)找出这些距离中最短路径为v1-v2，最短距离为L12=5，将v2标记为5V3V2V4V5V6V1V75155374648762045*(4)找出所有与v1,v2,v3相邻的未标记的点v4,v5,v6，求出从v1直接到这些点的距离(v1-v4:7)以及经过v2到这些点的距离(v1-v2-v4:11;v1-v2-v5:10;v1-v2-v6:8)以及经过v3到这些点的距离(v1-v3-v4:6;v1-v3-v5:12)找出这些距离中最短的路径为v1-v3-v4，最短距离为L14=6，将v4标记为6V3V2V4V5V6V1V751553746487620456*(5)找出所有与v1,v2,v3,v4相邻的未标记的点v5,v6，求出从v1经过v2到这些点的距离(v1-v2-v5:10;v1-v2-v6:8)以及经过v3到这些点的距离(v1-v3-v5:12)以及经过v4到这些点的距离(v1-v4-v5:13;v1-v4-v6:11)找出这些距离中最短的路径为v1-v2-v6，最短距离为L16=8，将v6标记为8V3V2V4V5V6V1V7515537464876204568*(6)找出所有与v1,v2,v3,v4,v6相邻的未标记的点v5,v7，求出从v1经过v2到这些点的距离(v1-v2-v5:10)以及经过v3到这些点的距离(v1-v3-v5:12)以及经过v4到这些点的距离(v1-v4-v5:13)以及经过v6到这些点的距离(v1-v2-v6-v5:9;v1-v2-v6-v7:14)找出这些距离中最短的路径为v1-v2-v6-v5，最短距离为L15=9，将v5标记为9V3V2V4V5V6V1V75155374648762045689*(7)找出所有与v1,v2,v3,v4,v5,v6相邻的未标记的点v7，求出从v1经过v5到这些点的距离(v1-v2-v6-v5-v7:13)以及经过v6到这些点的距离(v1-v2-v6-v7:14)找出这些距离中最短的路径为v1-v2-v6-v5-v7，最短距离为L15=13，将v7标记为13。至此所有点都已标记，即求出了v1到所有其他点的最短路径V3V2V4V5V6V1V7515537464876204568913*Dijkstra算法练习求如图所示的从v1到其他点的最短路径及路长.3273221v1v2v3v5v6v436*搬家公司最短路径问题的数学模型决策变量：图中每条边最短路是否经过 顶点v2v3v4v5v6v7v1v2v3v4v5v6*目标函数：经过的距离最短约束条件：从v1出去的边只能有一条：到达v7的边只能有一条：进出其他顶点的边数量相等：0-1约束：*求解结果V3V4V5V6V1V75155