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

王林
リリース: 2023-09-19 16:03:33
オリジナル
591 人が閲覧しました

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 サイトの他の関連記事を参照してください。

ソース:php.cn
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
最新の問題
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート
私たちについて 免責事項 Sitemap
PHP中国語ウェブサイト:福祉オンライン PHP トレーニング,PHP 学習者の迅速な成長を支援します!