当前位置:   article > 正文

最短路径(Dijkstra)算法_最短路径dijkstra算法

最短路径dijkstra算法

目录

一、Dijkstra算法

二、核心思路

三、步骤

四、代码


一、Dijkstra算法

迪杰斯特拉(Dijkstra)算法是由荷兰计算机科学家狄克斯特拉于1959年提出的。是寻找从一个顶点到其余各顶点的最短路径算法,可用来解决最短路径问题

二、核心思路

迪杰斯特拉算法采用贪心算法的策略,将所有顶点分为已标记点未标记点两个集合,从起始点开始,不断在未标记点中寻找距离起始点路径最短的顶点,并将其标记,直到所有顶点都被标记为止。

所以我们需要准备一个起始点到其他点最短距离的一张表,和一个挑选节点的表,如下

  1. //从headnode出发到所有点最小距离的表
  2. //key: 从headnode出发到达key的点
  3. //value: 从headnode出发到达key的最小距离
  4. unordered_map<Node*, int> distanceMap;
  5. //先放入头节点,头节点到头节点的距离为0,其他为解锁的节点距离为正无穷
  6. distanceMap.insert(make_pair(headnode, 0));
  7. //有一个记录节点的表,使用完一个节点之后放入表中不再使用
  8. set<Node*> selectNode
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/很楠不爱3/article/detail/710942
推荐阅读
相关标签
  

闽ICP备14008679号