C++ でダイクストラのアルゴリズムを使用する方法

C でダイクストラのアルゴリズムを使用するにはどうすればよいですか?

ダイクストラのアルゴリズムは、重み付き有向グラフ内の 2 つの頂点間の最短経路を見つけるために使用される貪欲なアルゴリズムです。その中心となるアイデアは、開始頂点から他の頂点までの最短距離を継続的に更新することで、最短パスを徐々に拡張することです。

以下では、C を使用してダイクストラのアルゴリズムを実装する方法と、具体的なコード例を紹介します。

ダイクストラのアルゴリズムを実装するには、次の手順が必要です。

ステップ 1: 初期化。

まず、開始頂点 start、最短距離配列 dist、アクセス ステータス配列など、いくつかのデータ構造を初期化する必要があります。開始頂点 start は最短パスの開始点を指定し、最短距離配列 dist は開始頂点から他の頂点までの現在の最短距離を記録するために使用され、アクセス ステータス配列 Visited は頂点が訪問されたかどうかをマークするために使用されます。 。

ステップ 2: 最短距離配列を初期化します。

開始頂点から他の頂点までの最短距離を無限大に初期化し、開始頂点からそれ自体までの最短距離を 0 に初期化します。また、開始頂点を訪問済みとしてマークします。

ステップ 3: 最短距離配列を更新します。

開始頂点に隣接するすべての頂点について、開始頂点を通るより短いパスが見つかった場合は、最短距離配列を更新します。具体的な更新方法は、開始頂点から現在の頂点までの距離と、開始頂点から現在の頂点までのエッジの重みを加算し、現在の頂点からの元の最短距離と比較することです。

ステップ 4: 次に近い頂点を選択します。

未訪問の頂点の中から開始頂点に最も近い頂点を次に訪問する頂点として選択します。

ステップ 5: ステップ 3 と 4 を繰り返します。

すべての頂点を訪問するまで、手順 3 と 4 を繰り返します。最後に、最短距離配列 dist に格納されるのは、開始頂点から各頂点までの最短距離です。

次は、C を使用してダイクストラのアルゴリズムを実装するコード例です:

#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;
}

上記のコードでは、2 次元行列を通じて重み付き有向グラフを表します。行列の各要素要素は 2 つの頂点間のエッジの重みを表します。最後に、開始頂点から各頂点までの最短距離を出力します。

以上がC++ でダイクストラのアルゴリズムを使用する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。