你的位置: 首页 > 通信技术 > 计算机网络

Dijkstra链路状态算法的运行过程

2016-11-23 16:48:57 | 人围观 | 评论:

Dijkstra链路

首先,引进一个辅助向量D,它的每个分量D[i]表示当前所找到的从始点v到每个终点vi的的长度:如D[3]=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于长度。它的初始状态为:若从v到vi有弧,则D为弧上的权值;否则置D为∞。显然,长度为 D[j]=Min{D | vi∈V} 的路径就是从v出发的长度最短的一条。此路径为(v,vj)。 那么,下一条长度次短的是哪一条呢?假设该次短路径的终点是vk,则可想而知,这条路径或者是(v,vk),或者是(v,vj,vk)。它的长度或者是从v到vk的弧上的权值,或者是D[j]和从vj到vk的弧上的权值之和。 一般情况下,假设S为已求得的终点的集合,则可证明:下一条最短路径(设其终点为X)或者是弧(v,x),或者是中间只经过S中的顶点而最后到达顶点X的路径。因此,下一条长度次短的的长度必是D[j]=Min{D | vi∈V-S} 其中,D或者是弧(v,vi)上的权值,或者是D[k](vk∈S)和弧(vk,vi)上的权值之和。算法描述如下: 1)arcs表示弧上的权值。若不存在,则置arcs为∞(在本程序中为MAXCOST)。S为已找到从v出发的的终点的集合,初始状态为空集。那么,从v出发到图上其余各顶点vi可能达到的度的初值为D=arcs[Locate Vex(G,v),i] vi∈V 2)选择vj,使得D[j]=Min{D | vi∈V-S} 3)修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。





标签:

相关内容推荐: