91超碰碰碰碰久久久久久综合_超碰av人澡人澡人澡人澡人掠_国产黄大片在线观看画质优化_txt小说免费全本

溫馨提示×

C++ Dijkstra算法怎樣實現圖的輸入

c++
小樊
82
2024-07-25 17:32:13
欄目: 編程語言

在C++中,可以使用鄰接矩陣或鄰接表來表示圖,并實現Dijkstra算法。以下是使用鄰接表表示圖的示例代碼:

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

using namespace std;

struct Node {
    int dest;
    int weight;
};

class Graph {
private:
    int V;
    vector<vector<Node>> adjList;

public:
    Graph(int vertices) {
        V = vertices;
        adjList.resize(V);
    }

    void addEdge(int src, int dest, int weight) {
        Node node = { dest, weight };
        adjList[src].push_back(node);
    }

    void dijkstra(int src) {
        vector<int> dist(V, INT_MAX);
        dist[src] = 0;

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({ 0, src });

        while (!pq.empty()) {
            int u = pq.top().second;
            pq.pop();

            for (Node neighbor : adjList[u]) {
                int v = neighbor.dest;
                int weight = neighbor.weight;

                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.push({ dist[v], v });
                }
            }
        }

        cout << "Shortest distances from source " << src << " to other vertices:" << endl;
        for (int i = 0; i < V; i++) {
            cout << "Vertex " << i << ": " << dist[i] << endl;
        }
    }
};

int main() {
    Graph g(6);

    g.addEdge(0, 1, 5);
    g.addEdge(0, 2, 3);
    g.addEdge(1, 3, 6);
    g.addEdge(1, 4, 2);
    g.addEdge(2, 1, 1);
    g.addEdge(2, 4, 4);
    g.addEdge(3, 5, 8);
    g.addEdge(4, 5, 7);

    g.dijkstra(0);

    return 0;
}

在這個示例中,首先創建一個Graph類來表示圖,其中包括頂點數量V和鄰接表adjList。addEdge函數用于添加邊,dijkstra函數用于計算從源頂點到其他頂點的最短路徑。

在main函數中,創建一個Graph對象并添加邊,然后調用dijkstra函數計算最短路徑。輸出結果為從源頂點0到其他頂點的最短距離。您可以根據自己的需求修改頂點數量和邊的權重來自定義圖。

0
襄汾县| 手机| 峡江县| 丹凤县| 日照市| 贞丰县| 阳高县| 象山县| 柳林县| 炉霍县| 邓州市| 西青区| 电白县| 博野县| 平昌县| 黎城县| 张家界市| 介休市| 巨野县| 乐都县| 休宁县| 隆回县| 军事| 秦皇岛市| 进贤县| 信丰县| 福清市| 霞浦县| 锦州市| 恩平市| 德化县| 呼伦贝尔市| 玉门市| 泾川县| 龙州县| 安远县| 河北省| 江门市| 宁城县| 澄城县| 灵山县|