圖的最短路徑算法在C++中的實(shí)現(xiàn)

以下是一個(gè)在C++中實(shí)現(xiàn)圖的最短路徑算法的示例代碼，使用Dijkstra算法來(lái)計(jì)算從源節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最短路徑：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

#define INF INT_MAX

// 定義圖的數(shù)據(jù)結(jié)構(gòu)
struct Edge {
    int to;
    int weight;
};

// Dijkstra算法函數(shù)
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() {
    // 構(gòu)建圖
    int n = 5; // 節(jié)點(diǎn)個(gè)數(shù)
    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});
    
    // 計(jì)算最短路徑
    vector<int> shortestPaths = dijkstra(graph, 0);
    
    // 輸出結(jié)果
    for (int i = 0; i < n; i++) {
        cout << "Shortest path from node 0 to node " << i << ": " << shortestPaths[i] << endl;
    }
    
    return 0;
}

在上面的代碼中，首先定義了一個(gè)圖的數(shù)據(jù)結(jié)構(gòu)Edge，然后實(shí)現(xiàn)了Dijkstra算法的函數(shù)dijkstra來(lái)計(jì)算最短路徑。最后在main函數(shù)中構(gòu)建了一個(gè)圖，計(jì)算了從節(jié)點(diǎn)0到其他節(jié)點(diǎn)的最短路徑，并輸出結(jié)果。

注意，以上示例代碼只是一個(gè)簡(jiǎn)單的示例，實(shí)際應(yīng)用中可能需要根據(jù)具體情況進(jìn)行修改和優(yōu)化。