単一ソース最短パスのDijkstraアルゴリズム

単源最短経路を解決する常用アルゴリズムはDijkstraアルゴリズムであり,Dijkstraアルゴリズムの主な構想は,まず長さが最も短い最短経路を求め,次に長さが次に短い最短経路を求め,原点から他のすべての頂点までの最短経路が求められるまで順次類推することである.構想の詳細説明:(1)現在取得されている最短経路の点セットを記録するために1セットのSを使用し、最初に始点V 0をSに入れ、すなわちV 0からV 0までの最短経路が0であるため、V 0からV 0までの最短経路が得られたことを意味する.1次元配列D[n]を使用して、V 0点から他の点までの最短距離を記録します.この初期化の設定は、点V 0がVnに直接接続されている場合、距離はこのエッジの重みであり、そうでない場合は無限です.(2)第1の最短経路を求め、第1の最短経路がV 0から他の点までの最短経路であれば、この経路を選択した点V nが集合Sに加わる.このとき、集合Sにおける点は依然として全ての最短距離が得られており、この新たに加えられた点Vnについては、V 0との最短経路が直接経路D 0 nとなる.(3)V 0から他の点までの最短距離、すなわち配列D[n]の値を更新する.S[n]配列に新たに点Kが加わったため、原点からS集合外の点Iまでの最短経路は、前のS集合から点Iまでの最短経路、またはK点が加わった後にK点を通過する経路が最短となる可能性がある.従って、D[i]=min{D[i],D[k]+A[k][i]を更新する},Aはすべてのエッジを記録する2次元配列である.最短距離を更新し、現在のD配列の値を常に最短経路とし、集合S中の点を原点として通過する点が点Iに到達する最短距離とする.(4)最短経路を求め、3で得られた最短経路をもとに、次の最短経路を求め続け、新たな点をS集合に加えて実行する(3)(5)目標点VtがS集合に加わるまで、更新された最短経路は、原点V 0から目標点Vtまでの最短経路である.
アルゴリズムの実現:(1)データ構造の選択:二次元配列A[n][n]を用いて現在の全ての有向経路を記録し、接続されていない2点に対して正無限に設定する.現在決定されている最短経路の点の集合をS[n]配列を用いて記録し、現在のソース点から他の点までの最短距離を配列D[n]で記録し、経路を配列path[n]で記録する.[n]の値は、原点から点nまでの最短経路における点nの前の点、すなわち、最後に完全なpath配列が得られた後、目標点から順に前に進むことで完全な経路が得られる.(2)データの初期化:S配列はboolタイプの配列であり、初期化はfalseであり、D[i]はA[v][i]であり、ここでvはソース点である.i!=vかつd[i]が無限でなければpath[i]=v、そうでなければpath[i]=-1、ここでは2点が直接接続されている場合、最短距離の前の点が原点であり、そうでなければ-1に設定される.(3)ソース点vを集合Sに加える:s[v]=true.(4)forループを使用する:現在最小のd[k]を選択し、ここで最も短い経路である点kを集合Sに計上し、s[k]を設定する=true,タグ点kは既に集合Sに加えられており,DとPath配列を巡回し,点Kに加えられた最短距離と最短経路の前のノードを更新する.ターゲット点が集合Sに入って終了するか,すべての点を集合Sに入れて終了するかを選択する.最短経路を得る.
次に、C++コードを使用した実装を行います.

template <class T>
int Choose(int *d ,bool * s){
    int i,minpos;
    T min;
    min = INFTY;
    minpos = -1;
    for(i = 0 ; i < n;i++)
        if(d[i] <= min && !s[i])
            min = d[i];minpos = i;
    return minpos;
}

template <class T>
void Dijkstra(int v,T* d ,int* path){
    int i,k,w;
    if(v<0|| v> n-1) throw OutOfBounds;
    bool *s = new bool[n];
    for(i = 0 ; i < n ; i++){
        s[i] = false;
        d[i] = a[v][i];
        if(i!=v && d[i] < INFTY) path[i] = v;
        else path[i] = -1;
    }
    s[v] = true;
    d[v] = 0;
    for(i = 0 ; i < n ; i++){
        k = Choose(d,s);
        s[k] = true;
        for(w = 0 ; w < n ; w++)
            if(!s[w] && d[k] + a[k][w] < d[w]){
                d[w] = d[k] + a[k][w];
                path[w] = k;
            }
    }
}