如何使用C++中的Dijkstra演算法

如何使用C 中的Dijkstra演算法？

Dijkstra演算法是一種用於求解帶權重有向圖中兩個頂點之間最短路徑的貪心演算法。它的核心思想是透過不斷更新起始頂點到其他頂點的最短距離來逐步擴展最短路徑。

以下將介紹如何使用C 實作Dijkstra演算法，並給出具體的程式碼範例。

實作Dijkstra演算法需要以下步驟：

Step 1：初始化。

首先，我們需要初始化一些資料結構，包括起始頂點start、最短距離數組dist和訪問狀態數組visited。起始頂點start指定了最短路徑的起點，最短距離數組dist用於記錄起始頂點到其他頂點的當前最短距離，訪問狀態數組visited用於標記頂點是否已經被訪問過。

Step 2：初始化最短距離陣列。

將起始頂點到其他頂點的最短距離初始化為無限大，起始頂點到自身的最短距離初始化為0。同時將起始頂點標記為已存取。

Step 3：更新最短距離陣列。

對於起始頂點相鄰的所有頂點，如果透過起始頂點能夠找到更短的路徑，則更新最短距離數組。具體的更新方式是將起始頂點到目前頂點的距離加上起始頂點到目前頂點的邊的權重，與目前頂點原始的最短距離進行比較。

Step 4：選取一個最近頂點。

從尚未造訪的頂點中選取距離起始頂點最近的頂點作為下一個要存取的頂點。

Step 5：重複步驟3和步驟4。

重複步驟3和步驟4，直到所有的頂點都被存取過。最終，最短距離數組dist中儲存的即為起始頂點到各個頂點的最短距離。

下面給出一個使用C 實作Dijkstra演算法的程式碼範例：

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

using namespace std;

vector<int> dijkstra(vector<vector<int>>& graph, int start) {
    int numVertices = graph.size();

    vector<int> dist(numVertices, INT_MAX); // 最短距离数组
    vector<bool> visited(numVertices, false); // 访问状态数组

    dist[start] = 0;

    for (int i = 0; i < numVertices - 1; i++) {
        int minDist = INT_MAX;
        int minIndex = -1;
        
        // 选取下一个最近顶点
        for (int j = 0; j < numVertices; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                minIndex = j;
            }
        }

        visited[minIndex] = true;

        // 更新最短距离数组
        for (int j = 0; j < numVertices; j++) {
            if (!visited[j] && graph[minIndex][j] && dist[minIndex] != INT_MAX && dist[minIndex] + graph[minIndex][j] < dist[j]) {
                dist[j] = dist[minIndex] + graph[minIndex][j];
            }
        }
    }

    return dist;
}

int main() {
    vector<vector<int>> graph = {
        {0, 2, 4, 0, 0},
        {2, 0, 1, 3, 0},
        {4, 1, 0, 0, 2},
        {0, 3, 0, 0, 3},
        {0, 0, 2, 3, 0}
    };

    vector<int> shortestDist = dijkstra(graph, 0);

    cout << "起始顶点到各个顶点的最短距离：" << endl;
    for (int i = 0; i < shortestDist.size(); i++) {
        cout << "到顶点 " << i << " 的最短距离为：" << shortestDist[i] << endl;
    }

    return 0;
}

在上述程式碼中，我們透過一個二維矩陣表示帶權重的有向圖，矩陣中的每個元素表示兩個頂點之間的邊的權重。最終輸出起始頂點到各頂點的最短距離。

以上是如何使用C++中的Dijkstra演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！