圖的應用——最短路徑

最短路徑

• 典型用途：交通問題。如：城市A到城市B有多條線路，但每條線路的交通費（或所需時間）不同，那麼，如何選擇一條線路，使總費用（或總時間）最少？
• 問題抽象：在帶權有向圖中A點（源點）到達B點（終點）的多條路徑中，尋找一條各邊權值之和最小的路徑，即最短路徑。

最短路徑與最小生成樹不同，路徑上不一定包含n個頂點

兩種常見最短路徑問題

Dijkstra（迪傑斯特拉）算法 —— 單源最短路徑

算法思想

把圖中頂點集合分成兩組：

第一組為已求出其最短路徑的頂點集合S

第二組為尚未确定最短路徑的頂點集合U

1. 初始時，S隻包含源點，S={v}，U包含除v外的其他頂點；
2. 從U中選取一個距離最小的頂點k，把k加入到S中；
3. 以k作為新考慮的中間點，修改U中各頂點的距離；
4. 重複步驟 2、3 直到所有頂點都包含在S中

算法實作

算法流程圖

C++代碼實作

void ShortestPath_DIJ(AMGraph G, int v0){
    // 用Dijkstra算法求有向網G的v0頂點到其餘頂點的最短路徑 
    n = G.vexnum;  // G 中頂點個數
    for(v = 0; v < n; v++){
        // n 個頂點依次初始化
        S[v] = false;  // S 初始為空集
        D[v] = G.arcs[v0][v];  // 将v0到各個終點的最短路徑長度初始化  
        if(D[v] < MaxInt) Path[v] = v0;  // v0和v之間有弧，将v的前驅置為v0
        else Path[v] = -1;  // 如果v0和v之間無弧，則将v的前驅置為-1
    }
    S[v0] = true;  // 将v0加入S
    D[v0] = 0;  // 源點到源點的距離為0

    /*―開始主循環，每次求得v0到某個頂點v的最短路徑，将v加到S集―*/
    for(i = 1; i < n; i++){
        // 對其餘n-1個頂點，依次進行計算
        min = MaxInt;
        for(w = 0; w < n; w++)
            if(!S[w] && (D[w] < min)){
                v = w;
                min = D[w];  // 選擇一條目前的最短路徑，終點為v
            }
        S[v] = true;  // 将v加入S
        for(w = 0; w < n; w++)  // 更新從v0出發到集合V−S上所有頂點的最短路徑長度
            if(!S[w] && ((D[v] + G.arcs[v][w]) < D[w])){
                D[w] = D[v] + G.arcs[v][w];  // 更新D[w]
                Path[w] = v;  // 更新w的前驅為v
            }
    }
}           

Floyd（弗洛伊德）算法 —— 所有頂點間的最短路徑

每一對頂點之間的最短路徑

方法一：每次以一個頂點為源點，重複執行Dijkstra算法n次—— T(n)=O(n³)

方法二：弗洛伊德(Floyd)算法

算法思想：逐個頂點試探法

• 初始時設定一個n階方陣，令其對角線元素為0，若存在弧<Vi,Vj>，則對應元素為權值；否則為∞
• 逐漸試着在原直接路徑中增加中間頂點，若加入中間點後路徑變短，則修改之；否則，維持原值。
• 所有頂點試探完畢，算法結結束

typedef int Pathmatirx[MAXVEX][MAXVEX]
typedef int ShortPathTable[MAXVEX][MAXVEX]

/*- Floyd算法，求網圖G中各頂點v到其餘頂點w最短路徑P[v][w]及帶權長度D[v][w] -*/
void ShrotestPath_Floyd(MGraph G, Pathmatirx* P, ShortPathTable* D){
    int v, w, k;
    for(v = 0; v < G.numVertexes; ++v){
        // 初始化D與P
        for(w = 0; w < G.numVertexes; ++w){
            (*D)[v][w] = G.matirx[v][w];  // D[v][w]值即為對應點間的權值
            (*P)[v][w] = w;  // 初始化P

        }
    }

    for(k = 0; k < G.numVertexes; ++k)
        for(v = 0; v < G.numVertexes; ++v)
            for(w = 0; w < G.numVertexes; ++w)
                if((*D)[v][w] > (*D)[v][k] + (*D)[k][w]){
                    // 如果經過下标為k頂點路徑比原兩點間路徑更短
                    // 将目前兩點間權值設為更小的一個
                    (*D)[v][w] = (*D)[v][k] + (*D)[k][w];
                    (*P)[v][w] = (*P)[v][k];  // 路徑設定為經過下标為k的頂點
                }
}