最短路徑c++

以下是一個簡單的 C++ 程式，使用 Dijkstra 算法來找到最短路徑：

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

using namespace std;

const int MAXN = 1000;

vector<pair<int, int>> adj[MAXN]; // 鄰接表存儲圖
int dist[MAXN]; // 存儲每個點到起點的距離
bool visited[MAXN]; // 標記節點是否已被訪問過

void dijkstra(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 小根堆
    pq.push(make_pair(0, start)); // 將起點加入小根堆
    dist[start] = 0; // 起點到起點的距離為 0
    visited[start] = true; // 將起點標記為已訪問

    while (!pq.empty()) {
        int u = pq.top().second; // 取出當前最小距離的節點
        pq.pop();

        for (auto& e : adj[u]) { // 遍歷當前節點的鄰居節點
            int v = e.first;
            int weight = e.second;
            if (dist[v] > dist[u] + weight) { // 如果通過當前節點到鄰居節點的距離更短
                dist[v] = dist[u] + weight; // 更新鄰居節點到起點的距離
                pq.push(make_pair(dist[v], v)); // 將鄰居節點加入小根堆中
                visited[v] = true; // 將鄰居節點標記為已訪問
            }
        }
    }
}

int main() {
    int n, m, start;
    cin >> n >> m >> start; // 輸入圖的節點數和邊數以及起點編號
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w; // 輸入一條邊(u, v, w)，其中w為邊權值
        adj[u].push_back(make_pair(v, w)); // 將這條邊加入起點節點的鄰接表中
        adj[v].push_back(make_pair(u, w)); // 將這條邊加入終點節點的鄰接表中（如果起點和終點不是同一個節點）
    }
    dijkstra(start); // 調用dijkstra算法找到最短路徑並輸出結果
    for (int i = 1; i <= n; i++) {
        cout << "Distance from " << start << " to " << i << " is " << dist[i] << endl; // 輸出每個點到起點的最短距離
    }
    return 0;
}

該程式使用鄰接表存儲圖，並使用 Dijkstra 算法來找到最短路徑。在主函式中，首先輸入圖的節點數、邊數和起點編號，然後輸入每條邊的起點、終點和權值。最後調用 dijkstra 函式來找到最短路徑並輸出結果。