最短路径算法是图论中的核心内容，用于在加权图中寻找两个节点之间路径权值之和最小的路径。根据不同的应用场景，最短路径算法可以分为多种类型。
一、算法分类与特点
1. 单源最短路径算法（从一个固定起点出发）
Dijkstra算法：
- 适用条件：边权非负的有向图或无向图
- 时间复杂度：
• 基础实现：O(V2)
• 优先队列优化：O((V+E) log V)
• 斐波那契堆优化：O(V log V + E) - 核心思想：贪心策略，每次选择当前未访问节点中距离起点最近的节点
Bellman-Ford算法：
- 适用条件：允许负权边，但不能有负权环
- 时间复杂度：O(VE)
- 特点：可以检测负权环
SPFA算法：
- 适用条件：允许负权边，但不能有负权环
- 时间复杂度：平均O(E)，最坏O(V E)
- 特点：Bellman-Ford的队列优化版本
2. 多源最短路径算法（任意两点间）
Floyd-Warshall算法：
- 适用条件：任意权值图（可处理负权边）
- 时间复杂度：O(V3)
- 空间复杂度：O(V2)
- 特点：动态规划思想，代码简洁
二、算法详细解析
Dijkstra算法实现（C++优先队列版）
typedef pair<int, int> pii;
vector<int> dijkstra(vector<vector<pii>>& graph, int start) {
int n = graph.size();
vector<int> dist(n, INT_MAX);
priority_queue<pii, vector<pii>, greater<pii>> pq;
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
for (auto [v, w] : graph[u]) {
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
return dist;
}
Floyd算法实现（C++版）
void floyd(vector<vector<int>>& dist) {
int n = dist.size();
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
三、算法选择指南
| 场景 | 推荐算法 | 原因 |
|---|---|---|
| 非负权图，单源 | Dijkstra | 效率高 |
| 含负权边，单源 | Bellman-Ford/SPFA | 能处理负权 |
| 多源最短路径 | Floyd-Warshall | 直接计算所有点对 |
| 稀疏图 | SPFA | 平均效率高 |
| 稠密图 | Dijkstra | 更稳定 |
四、典型应用场景
- 地图导航：计算两点间最短行车路线（Dijkstra）
- 网络路由：寻找最优数据传输路径（Bellman-Ford）
- 交通规划：计算所有地点间的最短距离（Floyd）
- 游戏AI：寻路算法（A*算法，Dijkstra变种）
- 社交网络：计算人与人之间的”距离”（广度优先搜索）