现在的位置: 首页 > 综合 > 正文

迪杰斯特拉算法

2013年10月05日 ⁄ 综合 ⁄ 共 360字 ⁄ 字号 评论关闭

算法描述:
一、A->B=6,A->C=3
则A->C=3
二、C->B=2,C->D=3,C->E=4
则A->C->B=5。在这里还需要向上回溯一下,通过与A->B=6比较,5更小。下同
三、B->D=5,则A->C->B->D=10
但在第2步中,C->D=3,所以A->C->D=6更小
四、D->E=2,D->F=3,则A->C->D->E=8
但在第二步中C->E=4,所以A->C->E=7更小
五、E->F=5,则A->C->E->F=12
但在第四步中D->F=3,所以A->C->D->F=9更小

基本思想:

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,

把图中顶点V分成两组:

  (1)S:已求出最短路径的顶点的集合

  (2)V-S=T:尚未确定最短路径的顶点集合

  将T中顶点按最短路径递增的次序加入到S中

抱歉!评论已关闭.