图的最短路径算法在C++中的实现

以下是一个在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到其他节点的最短路径，并输出结果。

注意，以上示例代码只是一个简单的示例，实际应用中可能需要根据具体情况进行修改和优化。