Dijkstra算法（迪杰斯特拉算法）
2019-08-22 本文已影响0人
pujess
目的
找出图中所有结点与某一结点最短路径
步骤
——前提条件：“图”结构已经建好，将所有结点与初始结点距离存入数组a备用
- 找到初始顶点
- 找到一个与初始顶点距离最小的顶点V（通过数组a判断）
- 找到V顶点后，遍历V周围顶点
- 更新V周围顶点与初始顶点之间的距离
若：初始顶点到V顶点的距离 + V顶点到某个V周围顶点距离 < 原本存的此周围顶点到初始顶点的距离
则：更新那个周围顶点到初始顶点的距离。 - 重复第三步！
实现
| 步骤 | 内容 | 如何实现 |
|---|---|---|
| 1 | 找到初始顶点 | 将初始顶点的前驱赋值为自己 |
| 2 | 遍历顶点，找到一个与初始结点距离最小的顶点V | 1.用循环，循环所有顶点，最后得输出距离最小顶点 |
| 3 | 找到V顶点后，遍历V周围顶点，更新V周围顶点与初始顶点之间的距离 | 1.用循环，循环所有顶点 2.每次循环都对距离数组a更新一次 |
| 4 | 回到第三步 | 这是一个大循环（也是主循环），循环除了初始顶点之外的顶点 |
