図-最短パスの問題

あるソースポイントから残りの頂点への最短パス
ディジェストラアルゴリズム
ディジェストラアルゴリズムは,経路長が増加する順序で最短経路を生成するアルゴリズムである.(負の丸このアルゴリズムは無効です)
アルゴリズムの説明:

は、帯域重みの隣接行列arcsで帯域重み有向図を表し、arcs[i][j]で弧上の重み値を表すと仮定する.存在しなければarcs[i][j]は∞である、Sは既に見つかったv 0頂点からの最短経路の終点の集合であり、初期状態は空である.

v 0~V−Sの頂点からなる最短経路を選択し、vjをSに加える.

vjがSに加わることにより最短経路が変化し、v 0からV-Sまでの可能な最短経路

を修正する.

は、第2、3のステップn-1を繰り返す、v 0から図上の残りの頂点への最短経路は、順次インクリメントされたシーケンス

である.
このアルゴリズムは最終的に増加した最短パスシーケンスであり、各サイクルではまず残りのパスの中の最短パスを見つけ、残りの最短パスを更新し、選択ソートのように、選択の後の最小パスを前に置くたびに、ソースポイントから図の各頂点への最短パスである秩序シーケンスに至る.

/*
    G.arcs  :       
    vo :   
    P  :        
    D  :    v0  vi        
*/
void shortestPath_DLJ(MGraph G, int v0, PathMatrix &P, ShortPathTable &D) {
    /*
           v0        v     P[v]     D[v]
        P[v][w] true   w   v0  v            
        
        final[v] true        v0  v      ,
             v    S   
    */ 
    //    
    for(v = 0; v < G.vexnum; v++){
        final[v] = false;
        
        //  v0  v  ，   D[v]     ，   INFINITY
        //G.arcs      ，    INFINITY 
        D[v] = G.arcs[v0][v];
        
        //     
        for(w = 0; w < G.vexnum; w++) P[v][w] = flase;
        
        // D[v]   INFINTY，   v0  v  ，v0, v      
        if(D[v] < INFINTY){ P[v][v0] = true; P[v][v] = true;} 
    }
    
    //    ，v0   S  
    D[v0] = 0; final[v0] = true;
    
    //     ，     v0  v       ，  v    S 
    //   G.vexnum - 1    
    for(i = 1; i < G.vexnum; i++){
        //    v0     
        min = INFINTY;
        
        for(w = 0; w < G.vexnum; w++) 
            //    V-S  
            if(!final[v]){ v = w; min = D[w];}
        
        //   ，  v    S  
        final[v] = true;
        
        /*             
              v    S ，     v      
                    ，          
        */ 
        for(w = 0; w < G.vexnum; w++)
            if(!final[w] && min + G.arcs[v][w] < D[w]){
                D[w] = min + G.arcs[v][w];
                //  v0  v    P[v]   P[w] 
                //w      
                P[w] = P[v];
                P[w][w] = true; 
            } 
    }    
}

続きます...