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

迪杰斯特拉算法求最短路径

2018年05月10日 ⁄ 综合 ⁄ 共 212字 ⁄ 字号 评论关闭

问题:求解某个源点到其余各顶点的最小距离

算法思想:对于网N=(V,E),将N中的顶点分成两部分:

第一组S:已求出最短路径的终点

第二组V-S:尚未求出最短路径的终点

  (1)、 一开始只将源点v0加入S。

  (2)、找出最短距离v0-v(v属于S-V),将v加入S;

  (3)、更新相关边的最小距离(如:v0-v1=9999,v0-v=5,v-v1=10,那么v0-v0更新为15)

   (4)、重复(2)(3)直到所有点都加入S

代码


抱歉!评论已关闭.