Dijkstra算法
Dijkstra算法(迪杰斯特拉算法)是一种经典的单源最短路径算法,用于在加权图中找到从一个源点到所有其他顶点的最短路径。它要求图中不能有负权边,因为负权边可能会导致算法的贪心策略失效。
Dijkstra算法的基本思想
Dijkstra算法的核心思想是贪心算法,通过逐步扩展已知最短路径的集合,最终找到从源点到所有顶点的最短路径。
算法步骤:
-
初始化:
- 将源点到自身的距离设为0,即
dist[source] = 0
。 - 将源点到其他所有顶点的距离设为无穷大,即
dist[v] = +∞
。 - 使用一个优先队列(最小堆)来存储待处理的顶点,初始时将源点加入队列。
- 将源点到自身的距离设为0,即
-
松弛操作:
- 从优先队列中取出距离最小的顶点
u
。 - 对于顶点
u
的所有出边(u, v)
,尝试更新从源点到顶点v
的距离:if dist[u] + weight(u, v) < dist[v]: dist[v] = dist[u] + weight(u, v)
- 如果更新了
dist[v]
,则将顶点v
加入优先队列。
- 从优先队列中取出距离最小的顶点
-
重复上述过程,直到优先队列为空。
Dijkstra算法的实现
以下是Dijkstra算法的标准实现,使用优先队列(最小堆)来优化松弛操作。
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
const int MAXN = 100005; // 最大顶点数
const int INF = 0x3f3f3f3f; // 表示无穷大
struct Edge {
int to, weight;
};
vector<Edge> graph[MAXN]; // 邻接表存储图
int dist[MAXN]; // 存储从源点到每个顶点的最短距离
bool visited[MAXN]; // 标记顶点是否已经被处理
// Dijkstra算法
void dijkstra(int n, int source) {
// 初始化
for (int i = 1; i <= n; i++) {
dist[i] = INF;
visited[i] = false;
}
dist[source] = 0;
// 使用优先队列(最小堆)
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({0, source}); // {距离, 顶点}
while (!pq.empty()) {
int u = pq.top().second; // 当前顶点
int d = pq.top().first; // 当前顶点的距离
pq.pop();
if (visited[u]) continue; // 如果已经处理过,跳过
visited[u] = true;
// 遍历所有出边
for (const auto& edge : graph[u]) {
int v = edge.to;
int weight = edge.weight;
// 尝试松弛
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v}); // 将更新后的顶点加入队列
}
}
}
}
int main() {
int n, m, source;
cout << "Enter number of vertices and edges: ";
cin >> n >> m;
cout << "Enter source vertex: ";
cin >> source;
cout << "Enter edges (u, v, weight):" << endl;
for (int i = 0; i < m; i++) {
int u, v, weight;
cin >> u >> v >> weight;
graph[u].push_back({v, weight}); // 添加边
}
dijkstra(n, source);
cout << "Shortest distances from source vertex " << source << ":" << endl;
for (int i = 1; i <= n; i++) {
if (dist[i] == INF) {
cout << "Vertex " << i << ": No path" << endl;
} else {
cout << "Vertex " << i << ": " << dist[i] << endl;
}
}
return 0;
}
算法复杂度
- 时间复杂度:
- 如果使用普通数组实现,时间复杂度为 O(V²)。
- 如果使用优先队列(最小堆)实现,时间复杂度为 O(E + V log V),其中
E
是边数,V
是顶点数。
- 空间复杂度:O(V + E),主要用于存储图的邻接表和辅助数组。
适用场景
Dijkstra算法适用于以下场景:
- 图中不包含负权边。
- 需要快速计算从单个源点到所有其他顶点的最短路径。
- 图的边数较多,且顶点数较少(适合稀疏图)。
注意事项
-
负权边问题:
- Dijkstra算法不能处理负权边。如果图中可能包含负权边,应使用Bellman-Ford算法或SPFA算法。
-
图的表示:
- 在实际应用中,图可以用邻接表或邻接矩阵表示。邻接表更适合稀疏图,而邻接矩阵更适合稠密图。
-
优化:
- 如果图中包含大量顶点,但只有少数顶点需要计算最短路径,可以使用启发式算法(如A*算法)来进一步优化。
总结
Dijkstra算法是一种高效的单源最短路径算法,特别适合处理不包含负权边的图。它通过贪心策略逐步扩展已知最短路径的集合,并利用优先队列优化松弛操作,从而在大多数情况下能够快速找到最短路径。