Dijkstra算法

Dijkstra算法（迪杰斯特拉算法）是一种经典的单源最短路径算法，用于在加权图中找到从一个源点到所有其他顶点的最短路径。它要求图中不能有负权边，因为负权边可能会导致算法的贪心策略失效。

Dijkstra算法的基本思想

Dijkstra算法的核心思想是贪心算法，通过逐步扩展已知最短路径的集合，最终找到从源点到所有顶点的最短路径。

算法步骤：

初始化：
- 将源点到自身的距离设为0，即 dist[source] = 0。
- 将源点到其他所有顶点的距离设为无穷大，即 dist[v] = +∞。
- 使用一个优先队列（最小堆）来存储待处理的顶点，初始时将源点加入队列。
松弛操作：
- 从优先队列中取出距离最小的顶点 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;
}