2)在计算过程中,需要把ⅴ中“经判断为最短路 P途径之点望”和“尚未判断是否为最短路P途径 之点j区分开来,可设置集合I和J,前者归入 I,后者归入J,并令算法初始时,中仅包含 V其他点全在J中,然后随着求解过程的进 行,I中的点逐渐增加(相应J中的点逐渐减 少),直到终点Ⅴ归入I(相应J=中),此时 迭代结束。I称为已标号集合,J称为未标号集
17 ⑵ 在计算过程中，需要把V中“经判断为最短路 P途径之点i”和“尚未判断是否为最短路P途径 之点j”区分开来，可设置集合I和J,前者归入 I，后者归入J，并令算法初始时，I中仅包含 Vs，其他点全在J中，然后随着求解过程的进 行，I中的点逐渐增加（相应J中的点逐渐减 少），直到终点Vt归入I（相应J=φ），此时 迭代结束。I称为已标号集合,J称为未标号集 合
3)为区分中间点是否已归入中以及逆向求解 最短路的方便,可在归入I中的点V;上方给予 双标号(lV),此中表示从v到v最短路 的距离,而v则为从V到V最短路P中Ⅴ的前 途径点。 (4)为在计算机上实现上述求解思想,还需引入G 中各点间一步可达距离阵D=d)nxn此中 MEn d=1lo,能一步到达 a,还能一步到达
18 ⑶ 为区分中间点Vk是否已归入I中以及逆向求解 最短路的方便，可在归入I中的点Vj上方给予 双标号（l j , Vk），此中l j表示从Vs到Vj最短路 的距离，而Vk则为从Vs到Vj最短路P中Vj的前 一途径点。 ⑷ 为在计算机上实现上述求解思想，还需引入G 中各点间一步可达距离阵D=(dij)n×n，此中 |V|=n = i j w i j d i j i j ， 不能一步到达 ， 能一步到达
(5)以下介绍的是适用于弧权为正值的有向网络 中求最短有向路的 Dijkstra算法,又称双括号 法。事实上该算法亦适用于弧权为负值的有向 网络求最短路问题
19 ⑸ 以下介绍的是适用于弧权为正值的有向网络 中求最短有向路的Dijkstra算法，又称双括号 法。事实上该算法亦适用于弧权为负值的有向 网络求最短路问题
由图G建立一步可达距离阵D=(d1)nxm Dijkstra算法 (双括号法) 给Ⅴ(V括号(L,V=(0,s给出已标号集合 和未标号集合J的元素 对于给定的和J,确定集合A={a1V∈L,Ⅴ∈丹 计算距离mn{l+WV∈J}=4+W 给v括号(L,V)1=L+Whk =I+3 J=J- =φ或J 从V道向搜索双括号,可得最小路径络点及最小路距离 图 END
20 由图G建立一步可达距离阵D=(dij)n×n 给V1 (Vs )括号(l1 ,Vk )=(0,s)给出已标号集合 I和未标号集合J的元素 对于给定的I和J，确定集合A={aij |Vi∈I，Vj∈J} 计算距离 给Vk括号(lk ,Vh ) lk=lh + Whk I=I + {Vk } J=J – {Vk } A=φ 或 J＝φ 从Vt 逆向搜索双括号，可得最小路P途径各点及最小路距离 ENDij h hk i I l i +W J = l +W min{ | V } j N Y （二） Dijkstra算法 （双括号法） 图 一
例1(教材208页)求G的最短路,图G形如下形。 图( 解:利用上述 Dijkstra算法步骤可得表一所示求 解过程,并有最短路P:V65V4,1V32V1 最短距离P=2+1+5=8
21 例1（教材208页）求G的最短路， 图G形如下形。 解：利用上述Dijkstra算法步骤可得表一所示求 解过程，并有最短路P：V6 V4 V3 V1， 最短距离|P|=2+1+5=8。 5 1 2 图（一）