算法简介:图最短路径
算法简介:图最短路径
图最短路径相关算法
1. 深度优先搜索算法(DFS)
- 解决问题
求图中多源(全源)最短路问题 - 时间复杂度
纯算法时间复杂度O(N^2) - 代码示例
最短路径DFS—无向图和有向图
2. 广度优先搜索算法(BFS)
- 解决问题
求图中多源(全源)最短路问题 - 时间复杂度
纯算法时间复杂度O(N^2) - 特点
比深度优先算法块,更加适用于边权相同的情况 - 代码示例
最短路径BFS—无向图
3. Floyd-Warshall(弗洛伊德算法----只有五行的算法)
- 解决问题
求图中多源(全源)最短路问题 - 时间复杂度
O(N^3) - 特点
- 非常简单,只有五行
- 可以求图中全源最短路问题
- 也可以求单源最短路问题(指定一个顶点到其余各个顶点的最短路径)
- 图中边权可以有负值,但是不可以含有负权回路
- 代码示例
示例图：
.
示例代码:
Floyd-Warshall