[解析アルゴリズムプール]マルチストリーム&floydとshallアルゴリズム

昨日解答した問題を通して、Dijkstra、Floyd-Warshallのアルゴリズムに対する理解が不十分だと感じて、繰り返し勉強してコードで実現してみます!

Dijkstra

コンセプト

多翼点アルゴリズムの用途は、「ある頂点から別の点までの最小距離を知りたいとき」です.
昨日もすべての頂点から別の頂点までの最小距離が必要でしたが、アルゴリズムの使い道を把握していなかったので、わけがわからず数時間かけてマルチタスクをしました.
6つの頂点を共有するグラフィックで,ノード1からノード2,3,4,5,6までの最小コストを求めるとする.

初期状態はINFであり、これは、1から他の地点までの料金を計算するまで、出発地点1以外のすべての料金が行けないことを意味する.
この場合、現在のコストが最も低い起点1を中間点として選択し、1->1->(2-6)のコストを更新できます.1−>1−>2の場合、cost[1] + 간선(1->2)の値は0+5 = 5であり、現在のcost[2]の値INFよりも小さいため、cost[2] = 5に更新される.
1に接続された幹線値を適用していますが、アルゴリズムの統一性のために、そう考えるのはかえって簡単です.

このようなプロセスによって、ノード3,5は同様にコスト値を更新し、1から1までの幹線が存在しないノード4,6は依然としてコスト値INFを維持する.

次に、更新後のノードから、最もコストの低いノード、3から他のノードを選択します.cost[3] = 1は、高校3年生に接続された幹線値に応じて、格納されたコスト値よりも小さく更新することができる.

再更新されたノードでは,最小値を持つノード,2を経由するノードとして選択し,上記の手順を繰り返す.このとき、既に中間点として選択されている1,3以外の2,4,5,6の中から2を選択する.
更新コストの中で最もコストの低いノードを選択する場合、リニアサーチを使用すると、時間の複雑さがO(N^N)であり、ノードが多く幹線が少ない極端な場合に、非常に時間を浪費する不吉な兆候が生じる可能性があります.
従って、この場合、優先順位キューを使用すると、線形検索よりもコストが最も低いノードを迅速に見つけることができ、時間的複雑度O(N*logN)を満たし、効率を向上させることができる.

コード#コード#

void linearDijkstra(){
    vector<int> visited(6, false);
    vector<int> cost(6, INF);
    for (int i = 0; i < 6; ++i) {
        cost[i] = edge[start][i];
    }
    visited[0] = true;

    for (int i = 0; i < 6-2; ++i) {

        int minCost = INF;
        int middleNode;
        for (int j = 0; j < 6; ++j) {
            if ( !visited[j] && minCost > cost[j]){
                minCost = cost[j];
                middleNode = j;
            }
        }
        visited[middleNode] = true;

        for (int j = 0; j < 6; ++j) {
            if (j!=start && cost[middleNode] + edge[middleNode][j] < cost[j]){
                cost[j] = cost[middleNode] + edge[middleNode][j];
            }
        }
    }

    cout<<"------------ Linear Dijkstra -------------"<<'\n';
    for (int i = 0; i < 6; ++i) {
        cout<<cost[i]<<' ';
    }
    cout<<'\n';
}

void heapDijkstra() {
    vector<int> cost(6, INF);
    cost[start] = 0;
    priority_queue<pair<int, int>> pq; // <노드 번호, -비용> 저장
    pq.push(make_pair(start, 0));

    while (!pq.empty()){
        int middleNode = pq.top().first;
        int middleCost = -pq.top().second;
        pq.pop();

        if(middleCost > cost[middleNode]) continue;

        for (int i = 0; i < 6; ++i) {
            if (i!=start && edge[middleNode][i] != INF && middleCost+edge[middleNode][i] < cost[i]){
                cost[i] = middleCost + edge[middleNode][i];
                pq.push(make_pair(i, -(middleCost + edge[middleNode][i])));
            }
        }

    }

    cout<<"------------ Heap Dijkstra -------------"<<'\n';
    for (int i = 0; i < 6; ++i) {
        cout<<cost[i]<<' ';
    }
    cout<<'\n';

}

Floyd-Warshall Floyd and Shall

コンセプト

フロイドとシエルの用途は「すべての頂点から他の頂点への最小コストを知りたいとき」です.
つまり、ダエストラの拡張版…?承認
しかし、プロセスはずっと簡単です.
これは、すべての頂点に複数のアルゴリズムを適用するように、もちろんn*nサイズの2次元配列が必要です.

同じグラフを対象として、初期状態、すなわち更新前の料金が上図のようになります.幹線接続されていない隣接ノードの場合、そのコストは無限大(INF、非常に大きな値)となり、移動できないことを示します.
フロイドとシエルでは、私たちはすべての頂点を出発点にしなければならないので、コストが最も低い中間点を選ぶ理由はありません.どうせN*N個のチェックが確認されるから.
次に、1〜6のノードを中間点に順次配置し、cost[i][j]を最高値に更新する.中間点がkの場合、cost[i][j] > cost[i][k] + edge[k-j]であれば、cost[i][j]の値が更新されます.
すべての中間点kノードについて、更新コストスキームが完了した後、完了したcost[i][j]円ノードi->jに移動するコストが最も低い.

コード#コード#

void floydWarshall() {
    for (int middle = 0; middle < 6; ++middle) {
        for (int i = 0; i < 6; ++i) {
            for (int j = 0; j < 6; ++j) {
                if (edge[i][j] > edge[i][middle] + edge[middle][j]){
                    edge[i][j] = edge[i][middle] + edge[middle][j];
                }
            }
        }
    }

    cout<<"------------ Floyd Warshall -------------"<<'\n';
    for (int i = 0; i < 6; ++i) {
        for (int j = 0; j < 6; ++j) {
            if (edge[i][j]<INF) cout<<edge[i][j]<<' ';
            else cout<<"INF"<<' ';
        }
        cout<<'\n';
    }
    cout<<'\n';
}

完全な実行コード

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

using namespace std;

int start = 0;
int INF = 100000;
vector<vector<int>> edge;


void linearDijkstra(){
    vector<int> visited(6, false);
    vector<int> cost(6, INF);
    for (int i = 0; i < 6; ++i) {
        cost[i] = edge[start][i];
    }
    visited[0] = true;

    for (int i = 0; i < 6-2; ++i) {

        int minCost = INF;
        int middleNode;
        for (int j = 0; j < 6; ++j) {
            if ( !visited[j] && minCost > cost[j]){
                minCost = cost[j];
                middleNode = j;
            }
        }
        visited[middleNode] = true;

        for (int j = 0; j < 6; ++j) {
            if (j!=start && cost[middleNode] + edge[middleNode][j] < cost[j]){
                cost[j] = cost[middleNode] + edge[middleNode][j];
            }
        }
    }

    cout<<"------------ Linear Dijkstra -------------"<<'\n';
    for (int i = 0; i < 6; ++i) {
        cout<<cost[i]<<' ';
    }
    cout<<'\n';
}

void heapDijkstra() {
    vector<int> cost(6, INF);
    cost[start] = 0;
    priority_queue<pair<int, int>> pq; // <노드 번호, -비용> 저장
    pq.push(make_pair(start, 0));

    while (!pq.empty()){
        int middleNode = pq.top().first;
        int middleCost = -pq.top().second;
        pq.pop();

        if(middleCost > cost[middleNode]) continue;

        for (int i = 0; i < 6; ++i) {
            if (i!=start && edge[middleNode][i] != INF && middleCost+edge[middleNode][i] < cost[i]){
                cost[i] = middleCost + edge[middleNode][i];
                pq.push(make_pair(i, -(middleCost + edge[middleNode][i])));
            }
        }

    }

    cout<<"------------ Heap Dijkstra -------------"<<'\n';
    for (int i = 0; i < 6; ++i) {
        cout<<cost[i]<<' ';
    }
    cout<<'\n';

}

void floydWarshall() {
    for (int middle = 0; middle < 6; ++middle) {
        for (int i = 0; i < 6; ++i) {
            for (int j = 0; j < 6; ++j) {
                if (edge[i][j] > edge[i][middle] + edge[middle][j]){
                    edge[i][j] = edge[i][middle] + edge[middle][j];
                }
            }
        }
    }

    cout<<"------------ Floyd Warshall -------------"<<'\n';
    for (int i = 0; i < 6; ++i) {
        for (int j = 0; j < 6; ++j) {
            if (edge[i][j]<INF) cout<<edge[i][j]<<' ';
            else cout<<"INF"<<' ';
        }
        cout<<'\n';
    }
    cout<<'\n';
}

int main() {

    edge = { {0,5,1,INF,10,INF},
             {5,0,2,9,INF,INF},
             {1,2,0,3,4,7},
             {INF,9,3,0,INF,5},
             {10,INF,4,INF,0,INF},
             {INF,INF,7,5,INF,0}};

    linearDijkstra();
    heapDijkstra();
    floydWarshall();

    return 0;

}

reference

マルチアウトレットアルゴリズム
floydとshallアルゴリズム