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

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,最短路问题,1,最短路径问题的实例,搬家公司的最短路径安排,某搬家公司负责一户人家的搬家业务，从出发点,V1,到新居,V7,之间的各段路径距离如下图所示（单位：,km,）。请问搬家公司如何安排路径，使运输距离最短？,V3,V2,V4,V5,V6,V1,V7,5,1,5,5,3,7,4,6,4,8,7,6,赋权有向图,2,2,求解算法-Dijkstra算法,基本原理：,最短路的子路也是最短路。,V2,V3,V4,2,9,8,4,4,V1,易知v1到v4的最短路径为v1-v2-v3-v4，最短距离10,则v1到v3的最短路径肯定为v1-v2-v3,同样v1到v2的最短路肯定为v1-v2,3,实例的Dijkstra算法求解步骤,(1)从起点v1出发，易知v1到v1的最短距离L,11,=0，对v1标号0,V3,V2,V4,V5,V6,V1,V7,5,1,5,5,3,7,4,6,4,8,7,6,2,0,4,(2),找出同v1相邻的未标号的点有v2,v3,v4，求出从v1到其所有相邻点的距离(v1-v2:5;v1-v3:4;v1-v4:7)，距离最短路径为v1-v3，最短距离为L13=4，将v3标记为4,V3,V2,V4,V5,V6,V1,V7,5,1,5,5,3,7,4,6,4,8,7,6,2,0,4,5,(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标记为5,V3,V2,V4,V5,V6,V1,V7,5,1,5,5,3,7,4,6,4,8,7,6,2,0,4,5,6,(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标记为6,V3,V2,V4,V5,V6,V1,V7,5,1,5,5,3,7,4,6,4,8,7,6,2,0,4,5,6,7,(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标记为8,V3,V2,V4,V5,V6,V1,V7,5,1,5,5,3,7,4,6,4,8,7,6,2,0,4,5,6,8,8,(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标记为9,V3,V2,V4,V5,V6,V1,V7,5,1,5,5,3,7,4,6,4,8,7,6,2,0,4,5,6,8,9,9,(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到所有其他点的最短路径,V3,V2,V4,V5,V6,V1,V7,5,1,5,5,3,7,4,6,4,8,7,6,2,0,4,5,6,8,9,13,10,Dijkstra算法练习,求如图所示的从,v,1,到其他点的最短路径及路长.,3,2,7,3,2,2,1,v1,v2,v3,v5,v6,v4,3,6,11,搬家公司最短路径问题的数学模型,决策变量：图中每条边最短路是否经过,顶点,v2,v3,v4,v5,v6,v7,v1,v2,v3,v4,v5,v6,12,目标函数：经过的距离最短,约束条件：,从v1出去的边只能有一条：,到达v7的边只能有一条：,进出其他顶点的边数量相等：,0-1约束：,13,求解结果,V3,V4,V5,V6,V1,V7,5,1,5,5,3,7,4,6,4,8,7,6,V2,最短距离：13km,14,最短路问题的一般化数学模型,在赋权有向图D=(V,A)中，寻求从始点 到终点 的最短路问题，假设边 的权重为 。可以设决策变量为图中边 是否经过 的0-1变量，此时，最短路问题可转化为如下0-1整数规划问题。,s.t.,始点的流出量-流入量=1,终点的流出量-流入量=-1,其他点的流出量-流入量=0,15,赋权无向图的最短路径问题,V3,V2,V4,V5,V6,V1,V7,5,1,5,5,3,7,4,6,4,8,7,6,赋权无向图,16,数学模型,顶点,v2,v3,v4,v5,v6,v7,v1,v2,v3,v4,v5,v6,决策变量：图中每条边最短路是否经过,17,数学模型,s.t.,始点的流出量-流入量=1,终点的流出量-流入量=-1,其他点的流出量-流入量=0,目标函数：,18,最短路问题的应用,某公司正在研制一种有极好销售潜力的新产品。当研究工作接近完成时，公司获悉一家竞争者正计划生产这种产品。要突击赶制出这种产品以参与竞争，还有四个互不重叠的阶段。为了加快进度，每个阶段都可采取“优先”或“应急”的措施。不同的措施下每段工作所需要的时间（月）和费用（百万元）如小下表示。现有一千万元资金供这四个阶段使用，则每段应采取什么措施能使这种产品尽早上市。试将此问题化成最短路问题并求解。,阶段,措施,剩余研究,试制,工艺设计,生产与调拨,时间,费用,时间,费用,时间,费用,时间,费用,正常,5,1,优先,4,2,3,2,5,3,2,1,应急,2,3,2,3,3,4,1,2,19,将原问题转化为赋权有向图,转化的方法：网络结点编号用一对数字,(i,j),表示，其中,i,表示各个阶段，,j,表示该阶段末剩余资金；结点,(i,j),与结点,(i+1,k),之间的弧的权数，表示当采取“费用为,(j-k),百万元的措施”时第,i+1,段的工作所需的时间。设起点为,(0,10),，终点为,(4,0),。,20,0,10,v1,1,9,v2,1,8,v3,1,7,v4,5,4,2,2,7,2,6,v5,2,5,v6,2,4,v7,3,2,3,2,3,2,3,4,3,3,3,2,v8,3,1,v9,3,3,3,5,5,5,5,4,3,4,2,4,1,4,0,v10,2,2,2,2,1,1,1,初始有1千万,第1阶段采用正常措施后资金剩余9百万,第1阶段采用正常措施所需时间5个月,第1阶段采用优先措施后资金剩余8百万,第1阶段采用正常措施所需时间4个月,第4阶段后资金正好用完,3,0,3,21,问题的数学模型,决策变量：图中每条弧是否被最短路经过,顶点,v2,v3,v4,v5,v6,v7,v8,v9,v10,v1,v2,v3,v4,v5,v6,v7,v8,v9,22,目标函数：经过的时间最少,约束条件：,从v1出去的弧只有一条：,从v10进入的弧只有一条：,其他顶点进入的弧等于出去的弧：,0-1约束：,23,最短时间如下图,0,10,v1,1,9,v2,1,8,v3,1,7,v4,5,4,2,2,7,2,6,v5,2,5,v6,2,4,v7,3,2,3,2,3,2,3,4,3,3,3,2,v8,3,1,v9,3,3,3,5,5,5,5,4,3,4,2,4,1,4,0,v10,2,2,2,2,1,1,1,3,0,3,最短时间：10个月,24,实际每个阶段采用的措施,阶段,措施,费用,时间,研究,试制,设计,生产,应急,优先,应急,优先,3,2,4,1,2,3,3,2,25,