[管理学]最短路问题.ppt

第三、最短路的迭代计算公式 定理 对于非负权有向网络G=（V，A，W）中， vs到所有其它顶点的最长度按大小排列为 d0≤d1≤d2……≤dn ，假设 P1=P(vs,v1), P2=P(vs,v2)… Pk=P(vs,vk)已求出。并记 SK={vs,v1…vk} ， ，则第k+1最短路 的路长dk+1 可 以按式求得： DijksTra算法的步骤： 第一步（初始化） 令k=0, S(0) ={vs}(S是永久标号点的集合)， T(0)={vs,v1…vn}（T是临时标号点的集合）d(0)(vs) =0， d(0) (vi) =∞ (d(vi)是vi点赋予的路长的初始标号， i=1,2,…n )。 λ(vi) = vs (λ(vi) )是λ(vi)点被赋予的vs→vi路径的vi先驱 点号，resent= vs ( resent用于表示必威体育精装版获得永久标号 的顶点)。 第二步 k=k+1 于对所有临时标号 ，计算 如果 ，则 第三步 若vk 满足 则resent= vk, ， 。 若k=n，则结束，否则转第二步。 例 用DijksTra算法求下图的最短路 v1 v5 v4 v3 vs 2 15 2 7 3 4 6 35 5 v2 16 9 21 最短路的算法步骤如下： 第一轮 k=0 ， ， ， ，（ ） ， ，（ ） resent= vs 第二轮 k=1 标号如图 第三轮 k=2 标号如图 第四轮 k=3 标号如图 第五轮 k=4 标号如图 第六轮 k=5 标号如图 最后v4获得永久标号 算法结束。 8.3.3 最短路算法之二——逐次逼近算法 逐次逼近算法的基本步骤与思路如下： 第一步： 赋初值 k=1（ k为迭代步骤） 的含义为从v1点到vj点只含有一个弧的最短路的路长。 为从v1点到vj点只含有一个弧的最短路的终点vj的前一个顶点号。 第二步：递推 k=k+1 递推关系如式所示： （wij 为弧 的权） 同时，路径标号 如式所示。 （ ，即vl 是 中vj 的前一个顶点号） 第三步：判断 若对于 ,有 ，则算法结束。否则，进一步判断k是否为n-1，若是则说明网络存在负回路，否则转步骤二。 例题 v1 v5 v4 v3 vs 2 15 2 7 3 4 6 35 5 v2 16 9 21 逐次逼近法的例题的算法过程(表中空格为+∞) j i wij d1j (1) d1j (2) d1j (3) d1j (4) d1j (5) v1 v2 v3 v4 v5 v6 0 4 5 0 0 0 0 0 0 5 4 2 2 2 2 -3 0 7 5 5 5 5 5 0 2 6 9 7 7 7 0 12 12 9 9 0 15 13 13 λ1j (1) v1 v1 v1 v1 v1 v1 λ1j (1) v1 3 v1 v2 v3 v1 λ1j (1) v1 v3 v1 v2 v3 4 λ1j (1) v1 v3 v1 v2 v4 v4 λ1j (1) v1 3 v1 v2 v4 v4 为了加快收敛速度，可以利用如下的递推关系： 四、Floyd算法 网络G=（V，A，W），令D=(