![](https://csdnimg.cn/release/download_crawler_static/87561021/bg6.jpg)
以解决从确定的起始点到任何其他点的最短行程.下面我们来介绍这种算
法,设G =(V,E)是一个加权连通图.
第一步:首先确定起始点,将其放入确定集D .给每一个顶点设定一个
权数,若有边连接起点与该点,则把这边权数设定为这点的权数,若没有边
连接起点与该点,则设定该点的权重为∞(无穷),而且确定集中起点的权为
0,表示与起点的最短行程.每做一步都将把某个顶点加入确定集,并修正
所有点的权重.
第二步:把权重最小的顶点放入确定集D ,其权数仍做为它在确定集中
点的权——即是从起点到这一点的最短行程.对每一个没有被列入确定集的
点A ,我们考虑每一个确定集中的点B ,如果有边连接A 与B ,这样可以得到
B 的权与这点连接边的权的和,所有这样的和一定有最小的值,令其为A 的
新的权数,当然,如果确定集中没有点能有与之连接成边,则A 的权仍是无
穷.用式子写出应是:A 的新权数w(A)为:
w(A)=min{w(B)+w(e(B-A)):e(B-A)
∈E}
其中e(B-A)表示有边e连接B 与A 点,w(e)表示e的权.w(B)表示起点到确定
集点B 的最短行程.
第三步:反复进行第二步骤就可以不断地扩大确定集,直到所有顶点进
入确定集.
下面我们分别用 Dijkatra算法分析例1和例2.
例1解:
第一步:令D ={A} ,w(A)=0,
又w(B)=2,w(C)=8,w(D)=1,其余点的权均为无穷.这样的点排成
如下序列:
D ,B ,C ,E,F,G ,I,J,K ,F.
第二步(1)把D 放入确定集D ={A ,D}(w(D) =1,)w(B)=2,w(C)=8,
w(G)=10,其余的点权均为无穷.
(2)把B 放入确定集D ={A ,D ,B}(w(B)=2),w(E)=3,w(C)=8,w(G)
=10,其余的点权均为无穷.
(3)把E放入确定集D ={A ,D ,B ,E}(w(E)=3),w(I)=5,w(F)=6,
w(C)=8,w(G)=10,w(J)=12,其余点的权为无穷.
(4)把I放入确定集D ={A ,D ,B ,E,I}(w(I)=5),调整后各点的权如
下:
w(F)=6,w(C)=7,w(G)=10,w(J)=12,w(L)=14,其余点的权均为
无穷.
(5)把F放入确定集D ={A ,D ,B ,E,I,F}(w(F)=6),调整后各点的
权重为w(C)=7,w(G) =10,w(J)=12,w(L)=14,其余点的权为无穷.
(6)把C 放入确定集D ={A ,D ,B ,E,I,F,C}(w(C)=7),调整后各点
的权重为w(G)=10,w(J)=12,w(L)=14,w(K) =10;
(7)把G 放入确定集D ={A ,D ,B ,E,I,F,C ,G}(w(G) =10),
调整后各点的权重为w(K)=11,w(J)=12,w(L)=14;