最短路
从某顶点出发,沿图的边到达另一顶点所经过的路径中,各边上权值之和最小的一条路径叫做最短路径。
最短路算法根据应用场景,可选用Dijkstra算法、spfa算法和Floyd算法
1.Dijkstra 算法:
证明:
first–朴素:
应用场景:
用于稠密图,时间复杂度
Code:
1 | int dist[N]; // 储存到每个节点的最短路径 |
second–堆优化:
堆优化即为用堆将所有的距离进行维护,可降低查找当前最小距离的时间复杂度
由于
应用场景:
用于稀疏图,时间复杂度为
2. 算法:
3. 算法:
- 标题: 最短路
- 作者: firstlight
- 创建于 : 2023-09-28 21:50:00
- 更新于 : 2025-01-22 22:41:04
- 链接: https://blog.firstlightport.top/posts/zui-duan-lu/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论