电工学习网

 找回密码
 立即注册

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

2015-7-11 07:01| 编辑:电工学习网| 查看: 4531| 评论: 0

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可达的最短路径长度。

看过《Dijkstra链路状态算法的运行过程》的人还看了以下文章:

发表评论

最新评论

  • 如何识别网线的真假?
  • 网桥都是点对点传输吗?网桥传输方式
  • 家庭装修网线设计走线
  • 网线水晶头直通线和交叉线的接法图解
  • 计算机网络的组成部分
  • 网络协议与网络体系结构
热点文章

电工学习网 ( )

GMT+8, 2021-12-6 20:44

Powered by © 2011-2021 www.shop-samurai.com 版权所有 免责声明 不良信息举报

技术驱动未来! 电工学习网—专业电工基础知识电工技术学习网站。

栏目导航: 工控家园 | 三菱plc | 西门子plc | 欧姆龙plc | plc视频教程

返回顶部