77 lines
1.9 KiB
C++
77 lines
1.9 KiB
C++
//
|
|
// Created by grtsinry43 on 5/8/25.
|
|
//
|
|
|
|
#include <algorithm>
|
|
#include <climits>
|
|
#include <iostream>
|
|
#include <vector>
|
|
#include <queue>
|
|
using namespace std;
|
|
|
|
struct Edge {
|
|
int to, weight;
|
|
};
|
|
|
|
void dijkstra(int source, const vector<vector<Edge> > &graph) {
|
|
int n = graph.size();
|
|
vector<int> dist(n, INT_MAX); // 存储最短路径长度
|
|
vector<int> prev(n, -1); // 存储路径
|
|
dist[source] = 0;
|
|
|
|
// 优先队列，按距离从小到大排序
|
|
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<> > pq;
|
|
pq.push({0, source});
|
|
|
|
while (!pq.empty()) {
|
|
auto [d, u] = pq.top();
|
|
pq.pop();
|
|
|
|
if (d > dist[u]) continue;
|
|
|
|
for (const auto &edge: graph[u]) {
|
|
int v = edge.to, weight = edge.weight;
|
|
if (dist[u] + weight < dist[v]) {
|
|
dist[v] = dist[u] + weight;
|
|
prev[v] = u;
|
|
pq.push({dist[v], v});
|
|
}
|
|
}
|
|
}
|
|
|
|
// 输出结果
|
|
for (int i = 0; i < n; ++i) {
|
|
if (dist[i] == INT_MAX) {
|
|
cout << "Node " << i << " is unreachable from source " << source << ".\n";
|
|
} else {
|
|
cout << "Shortest distance to node " << i << " is " << dist[i] << ". Path: ";
|
|
vector<int> path;
|
|
for (int at = i; at != -1; at = prev[at]) {
|
|
path.push_back(at);
|
|
}
|
|
ranges::reverse(path.begin(), path.end());
|
|
for (int j = 0; j < path.size(); ++j) {
|
|
cout << path[j] << (j + 1 < path.size() ? " -> " : "\n");
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
int problem_1() {
|
|
int n = 5; // 节点数
|
|
vector<vector<Edge> > graph(n);
|
|
|
|
// 添加边 (示例)
|
|
graph[0].push_back({1, 2});
|
|
graph[0].push_back({2, 4});
|
|
graph[1].push_back({2, 1});
|
|
graph[1].push_back({3, 7});
|
|
graph[2].push_back({4, 3});
|
|
graph[3].push_back({4, 1});
|
|
|
|
int source = 0; // 源点
|
|
dijkstra(source, graph);
|
|
|
|
return 0;
|
|
}
|