当前位置: 代码迷 >> 综合 >> Dijkstra笔记
  详细解决方案

Dijkstra笔记

热度:26   发布时间:2024-01-15 21:25:18.0

Dijkstra算法是典型最短路径算法,用于计算一个节点到其他所有节点的最短路径。不过,针对的是非负值权边。

因为Dijkstra算法总是在V-S中选择“最轻”或“最近”的顶点插入到集合S中,所以我们说它使用了贪心策略。


自己捋一遍算法

1、初始化

有边(E)相连的点(V)之间weight设为对应值,不连通的点对间weight设为无穷大;

表征X点是否找到的数组final全部初始为0;final[出发点] = 1;

表征X点最小距离的数组dist全部初始化为无穷大;

2、循环 除初始点外所有点

从初始点找与初始点之间weight最小的点k,final[k] = 1, dist[k] = weight<初始点,k>;

从k出发,遍历所有点 ,看有没有哪个点X,能满足 dist[x] > dist[k] + weight<k, x>,如果有,dist[x]更新;如果没这轮小循环拉倒;