§3.最短路问题 最短路问题是网络理论中应用最广泛的问题之一,许多优化问题可以 使用这个模型,如管道铺设,设备更新,线路安排等。在第三章我们曾介 绍了最短路问题的动态规划解法,但某些最短路的问题构造动态规划基本 方程较困难,而图论方法则直观有效 给定D=(V,A,W),其中w∈W,表示弧(v,v)的权(可以是费用、时间 距离等)。设ⅴ和v是D中任意两顶点,求一条路,使它是从ⅴ到v的 所有路中总权最小的路。其数学模型为: W(P)=mn∑W (v,v)∈P W」≥0情况下,求最短路的 Di jkstra标号法 1该法的基本思想是基于以下原理:若序列{v,v,…vk,…v}是从w到 vt的最短路,则序列{vs,wi,…Vk}必为从vs到vk的最短路。 2 Dijkstra标号法的基本思想是采用两种标号:T标号与P标号,T标 号为临时性标号( Temporary Label,P标号为永久性标号( Permanent labe 从v开始,逐步向外探寻最短路。给ⅵ点P标号时,表示从v到ⅵ点的最 短路权,ⅵ的标号不再改变。给v点T标号时,表示从vs到w点的最短路 权上界的估计。凡没有得到P标号的点都有T标号。标号法每一步都是把 某一T标号点改为P标号,当终点vt得到P标号时,计算全部结束。如果 点ⅴ不能由T标号变为P标号,则说明ws到v不存在路 3.步骤: (1)给v以P标号,P(ⅴ)=0,其余各点给T标号,且T(v)=+ (2)若v点为刚得到P标号的点,考虑T标号点v(v,v)∈A。对v的T 标号进行如下的更改 T(vimin(T(v), P(vi)+wii (4.1)28 §3. 最短路问题 最短路问题是网络理论中应用最广泛的问题之一，许多优化问题可以 使用这个模型，如管道铺设，设备更新，线路安排等。在第三章我们曾介 绍了最短路问题的动态规划解法，但某些最短路的问题构造动态规划基本 方程较困难，而图论方法则直观有效。 给定 D=(V,A,W)，其中 wijW，表示弧(vi,vj)的权（可以是费用、时间、 距离等）。设 vs 和 vt 是 D 中任意两顶点，求一条路，使它是从 vs 到 vt 的 所有路中总权最小的路。其数学模型为： W P = min Wij ( ) * (vi,vj)P 一、Wij0 情况下，求最短路的 Dijkstra 标号法 1.该法的基本思想是基于以下原理：若序列{vs,vi1,…vik,…vt}是从 vs 到 vt 的最短路，则序列{vs,vi1,…vik}必为从 vs 到 vik的最短路。 2.Dijkstra 标号法的基本思想是采用两种标号：T 标号与 P 标号，T 标 号为临时性标号(Temporary Label)，P 标号为永久性标号(Permanent Label)。 从 vs 开始，逐步向外探寻最短路。给 vi 点 P 标号时，表示从 vs 到 vi 点的最 短路权，vi 的标号不再改变。给 vi 点 T 标号时，表示从 vs 到 vi 点的最短路 权上界的估计。凡没有得到 P 标号的点都有 T 标号。标号法每一步都是把 某一 T 标号点改为 P 标号，当终点 vt 得到 P 标号时，计算全部结束。如果 点 vj 不能由 T 标号变为 P 标号，则说明 vs 到 vj 不存在路。 3.步骤： (1)给 vs 以 P 标号，P(vs)=0，其余各点给 T 标号，且 T(vi)=+。 (2)若 vi 点为刚得到 P 标号的点，考虑 T 标号点 vj,(vi,vj)A。对 vj 的 T 标号进行如下的更改： T(vj)=min{T(vj),P(vi)+wij} (4.1)