离散数学CH04图论最短路径与关键路径

《离散数学CH04图论最短路径与关键路径》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学DiscreteMathematics计算机与信息工程学院第4章图论内容提要图的基本概念4.1连通图4.34.4图的矩阵表示路和回路4.2内容提要欧拉图和哈密顿图4.5二部图及匹配4.74.8平面图树4.6定义：设G=(V，E，)为无向简单图，对于每一条边e∈E，均有一个正实数W(e)与之对应，称w为G的权函数，并称G为带有权W的图，又称赋权图，权也称为边的长度。4.5最短路径及关键路径边(vi,vj)的权带权图求给定两点间的最短距离——两点之间的最短路径问题求从某个源点到其余各点的最短路径每一对顶点之间的最短

2、路径4.5最短路径及关键路径求从源点到其余各点的最短路径的算法的基本思想:依最短路径的长度递增的次序求得各条路径源点v1…其中，从源点到顶点v1的最短路径是所有最短路径中长度最短者。v24.5最短路径及关键路径在这条路径上，必定只含一条弧，并且这条弧的权值最小。下一条路径长度次短的最短路径的特点：路径长度最短的最短路径的特点：它只可能有两种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。4.5最短路径及关键路径其余最短路径的特点：再下一条路径长度次短的最短路径的特点:它

3、可能有三种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。它或者是直接从源点到该点(只含一条弧)；或者是从源点经过已求得最短路径的顶点，再到达该顶点。4.5最短路径及关键路径从源点到其余各点的最短路径Dijkstra算法（1959）设G有n个顶点；边的长度ℓij≥0；若结点vi和vj没有边相连(不是邻接点)，则令ℓij=∞，对每个结点vi，令ℓij=0。4.5最短路径及关键路径将顶点集V分成两部分，一部分成为具有P（永久性）标号的

4、集合，另一部分成为具有T（暂时性）标号的集合。所谓结点v的P标号是指从v1到v的最短路径的长度；而顶点u的T标号是指从v1到u某条路径的长度。Dijkstras算法首先将v1取为P标号，其余结点取为T标号，然后逐步将具有T标号的结点改为P标号。当结点vn已被改为P标号时，就找到了一条从v1到vn的最短路径。4.5最短路径及关键路径Dijkstras基本思路：Step1:初始化：将v1置为P标号，d(v1)=0，P={v1}，vi(i≠1)置vi为T标号，即T=V-P，且d(vi)=W(v1,vi)若viadjvid(v

5、i)=∞else4.5最短路径及关键路径Step2:找最小寻找具有最小值的T标号的结点。若为vl，则将vl的T标号改为P标号，且P=P∪{vl}，T=T-{vl}。Step3：修改修改与vl相邻的结点的T标号的值。viT：d(vi)=d(vl)+W(vl,vi)若d(vl)+W(vl,vi)

6、∞04(v1)P={v1}T={v2,v3,v4,v5,v6}4.5最短路径及关键路径P={v1,v2}T={v3,v4,v5,v6}(v1)∞03(v1,v2)18(v1,v2)6(v1,v2)4.5最短路径及关键路径P={v1,v2,v3}T={v4,v5,v6}(v1)∞0(v1,v2)18(v1,v2)4(v1,v2,v3)34.5最短路径及关键路径P={v1,v2,v3,v5}T={v4,v6}(v1)0(v1,v2)17(v1,v2,v3,v5)(v1,v2,v3)3410(v1,v2,v3,v5)4.5最短

7、路径及关键路径P={v1,v2,v3,v5,v4}T={v6}(v1)0(v1,v2)1(v1,v2,v3,v5)(v1,v2,v3)349(v1,v2,v3,v5)74.5最短路径及关键路径(v1)0(v1,v2)P={v1,v2,v3,v5v4,v6}T={}1(v1,v2,v3,v5)(v1,v2,v3)34(v1,v2,v3,v5,v4)794.5最短路径及关键路径10(v5)第1短V1V5V4V2V3V610101002050205030510v2v3v4v5v6step1503010010∞20(v4)第2短

8、step2503020∞30(v3)第3短step34030∞35(v2)第4短step4355045(v6)第5短step545/V1/V5/V1/V3/V24.5最短路径及关键路径2(v2)第1短v2v3v4v5v6v7step1253∞∞3(v4)第2短step243∞4(v3)第3短step384∞7(v5)