阅读量:0
以下是一个在C++中实现图的最短路径算法的示例代码，使用Dijkstra算法来计算从源节点到所有其他节点的最短路径：
#include <iostream> #include <vector> #include <queue> #include <climits> using namespace std; #define INF INT_MAX // 定义图的数据结构 struct Edge { int to; int weight; }; // Dijkstra算法函数 vector<int> dijkstra(vector<vector<Edge>>& graph, int source) { int n = graph.size(); vector<int> dist(n, INF); dist[source] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, source}); while (!pq.empty()) { int u = pq.top().second; pq.pop(); for (Edge& e : graph[u]) { int v = e.to; int weight = e.weight; if (dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; pq.push({dist[v], v}); } } } return dist; } int main() { // 构建图 int n = 5; // 节点个数 vector<vector<Edge>> graph(n); // 添加边 graph[0].push_back({1, 10}); graph[0].push_back({2, 5}); graph[1].push_back({2, 2}); graph[1].push_back({3, 1}); graph[2].push_back({1, 3}); graph[2].push_back({3, 9}); graph[2].push_back({4, 2}); graph[3].push_back({4, 4}); graph[4].push_back({3, 6}); // 计算最短路径 vector<int> shortestPaths = dijkstra(graph, 0); // 输出结果 for (int i = 0; i < n; i++) { cout << "Shortest path from node 0 to node " << i << ": " << shortestPaths[i] << endl; } return 0; } 在上面的代码中，首先定义了一个图的数据结构Edge，然后实现了Dijkstra算法的函数dijkstra来计算最短路径。最后在main函数中构建了一个图，计算了从节点0到其他节点的最短路径，并输出结果。
注意，以上示例代码只是一个简单的示例，实际应用中可能需要根据具体情况进行修改和优化。
