二.最短路问题 1.问题:求网络D中一定点v到其它点的最短路。 例3求如图网络中η至v的最短路,图中数字 为两点间距离。 5 2.方法:标号法( Dijkstra,1959) 给每点v标号团d,v,其中d为v1至v的最短距,v为 最短路上的前一点 2021/2/24
2021/2/24 二. 最短路问题 1. 问题：求网络D中一定点v1到其它点的最短路。 例3 求如图网络中v1至v7的最短路，图中数字 为两点间距离。 v5 v1 v3 v6 v4 v2 v7 2 5 5 2 3 3 5 7 5 7 1 1 2. 方法：标号法（Dijkstra，1959） 给每点vj标号[dj，vi ]，其中dj为v1至vj的最短距，vi为 最短路上的前一点
标号法步骤: 1.给ν,标号O,v,] 已标号点集, 2把顶点集V分为互补的两部分 未标号点集 3.考虑所有这样的边]其中v,∈,∈EV 挑选其中与v距最短(mn+c)的进行标号 4重复3,直至终点(本例即v,)标上号d,,则 d即最短距,反向追踪可求出最短路。 2021/2/24
2021/2/24 标号法步骤： 即最短距，反向追踪可求出最短路。 重复 ，直至终点（本例即 ）标上号 ，则 挑选其中与 距最短（ 的 进行标号。 考虑所有这样的边 其中 未标号点集； 已标号点集， 把顶点集 分为互补的两部分 给 标号 ， 4 . 3 [ , ] ) 3 . [ , ], , , : : 2 . 1 . [0 ]; 7 7 7 1 1 1 1 1 1 1 d v d v v d c v v v v V v V V V V v v min +