首页 > 编程语言 > 详细

图的最短路径——dijkstra算法和Floyd算法

时间:2019-03-02 13:29:10      阅读:234      评论:0      收藏:0      [点我收藏+]

dijkstra算法

  求某一顶点到其它各个顶点的最短路径;已知某一顶点v0,求它顶点到其它顶点的最短路径,该算法按照最短路径递增的顺序产生一点到其余各顶点的所有最短路径。

对于图G={V,{E}};将图中的顶点分为两组:

  第一组S:求出已知顶点的最短路径的集合

  第二组V-S:尚未求出最短路径的顶点集合(开始为V-{v0}的全部顶点)

该算法将最短路径以递增顺序逐个将第二组顶点加入到第一组顶点中,直到所有的顶点都被加入到第一组顶点集S为止

图的最短路径——dijkstra算法和Floyd算法

原文:https://www.cnblogs.com/tianzeng/p/10460544.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!