图论与网络优化课件.ppt

* 最短路问题按其不同的要求，可分成下列三种类型： 1、求两个定点之间的最短路； 2、求一个定点到其他各点的最短路； 3、求各点对之间的最短路。 不失一般性，总假定图中无环，以及多重弧只是由两条互为反向的弧组成的二重弧。 * 【例4】（渡河问题） 一人携带狼、羊、菜，须从一条小河的此岸渡往对岸。河边仅有一条小船，容量为2。当人不在场时，狼要吃羊、羊要吃菜。问：应怎样渡河，才能使大家安全到达对岸，且小船在河上的来回次数最少。 (船上必须要有人) * 【解】 记M代表人、W代表狼、S代表羊、V代表菜。 以河的此岸为考察基点，则开始状态为MWSV，结束状态为Φ。 共有16种状态：MWSV、MWS、MWV、MSV、WSV、MW、MS、MV、WS、WV、SV、M、W、S、V、Φ。 其中，有6种不允许出现，即：WSV、MW、MV、WS、SV、M。 于是，可能的状态仅有10种。 * 以每个状态作为顶点，构造相应的图（如图5-8所示），其中，边的连接原则为： 若状态甲经一次渡河可变为乙，则连一条边。 从而，渡河问题就归结为求MWSV→Φ的最短路。 (船上必须要有人) （算法形式化方面的内容） 图5-8 MWSV MWS MWV MSV MS WV W S V Φ * 三、有向图最短路算法 1964年，Ford提出了可求解含负权的最短路问题的递推标号法。 设赋权有向图D = (V, A, W)，V中含p个点，现要求始点v1至终点vp的最短路Rp*及其路长rp*。假定D中无负回路（其上总权为负数的回路），将原弧集A增广为新弧集，以使V中任意两点间均有互为反向的两条弧，同时权集W增广为新权集。于是，原图D增广为新图 。 * 其中，当i = j时，若设 ，则与实际背景不符，若 0，则出现负回路，故须定义为0。由Bellman最优化原理易知：从v1到vj的最短路长rj*必满足 ,反之亦然。 显见，若某两相邻点之间有多于一条的同向弧，则可弃大留小，简化为一条弧，从而是一个完全的二重赋权有向图，其中，增广的权集，定义为： 例：最短路径引例 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 求从1到8的最短路径 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1}, w1=0 min {c12,c14,c16}=min{0+2,0+1,0+3}=min{2,1,3}=1 其他为∞ X={1,4}, w4=1 w1=0 w1=0 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,4} min {c12,c16,c42,c47}=min {0+2,0+3,1+10,1+2}=min {2,3,11,3}=2 X={1,2,4}, w2=2 w1=0 w4=1 w2=2 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4} min {c16,c23,c25,c47}=min {0+3,2+6,2+5,1+2}=min {3,8,7,3}=3 X={1,2,4,6}, w6=3 w2=2 w4=1 w1=0 w6=3 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4,6} min {c23,c25,c47,c67}=min {2+6,2+5,1+2,3+4}=min {8,7,3,7}=3 X={1,2,4,6,7}, w7=3 w2=2 w4=1 w1=0 w6=3 w7=3 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4,6,7} min {c23,c25,c75,c78}=min {2+6,2+5,3+3,3+8}=min {8,7,6,11}=6 X={1,2,4,5,6,7}, w5=6 w2=2 w4=1 w1=0 w6=3 w7=3 w5=6 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4,6,7} min {c23,c53,c58,c78}=min {2+6,6+9,6+4,3+8}=min {8,15,10,11}=8 X={1,2,3,4,5,6,7}, w3=8 w2=2 w4=1 w1