資料結構基礎6.4：最短路徑（Dijkstra, Floyd）

一. Dijkstra算法：

1. 定義：

Dijkstra算法是典型的單源最短路徑算法，用于計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴充，直到擴充到終點為止。Dijkstra算法是很

有代表性的最短路徑算法，在很多專業課程中都作為基本内容有詳細的介紹，如資料結構，圖論，運籌學等等。注意該算法要求圖中不存在負權邊。

該算法用于解決單源最短路徑。

2. 算法描述：

類似于Prim算法，設G=(V,E)是一個帶權有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中隻有一個源點，以後每求得一條

最短路徑 , 就将加入到集合S中，直到全部頂點都加入到S中，算法就結束了），第二組為其餘未确定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二

組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，S中的頂點的

距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點隻包括S中的頂點為中間頂點的目前最短路徑長度。

3. 代碼實作:

/* 最短路徑Dijkstra算法 */
Status Dijkstra(MGraph graph, Vertex n)
{
    int i, j, min = INF, index, p;
    bool marked[MaxVertexSize];
    int P[MaxVertexSize];
    int cost[MaxVertexSize];
    
    if(n < 0 || n >= graph->Nv)
        return ERROR;
        
    for(i = 0; i < graph->Nv; i++) {
        marked[i] = false;
        cost[i] = graph->matrix[n][i];
        P[i] = n;
    }
    marked[n] = true;
    
    for(i = 0; i < graph->Nv - 1; i++) {
        min = INF;
        
        for(j = 0; j < graph->Nv; j++) {
            if(!marked[j] && cost[j] < min) {
                min = cost[j];
                index = j;
            }
        }

        marked[index] = true;
        
        for(j = 0; j < graph->Nv; j++) {
            if(!marked[j] && graph->matrix[index][j] + min < cost[j]) {
                cost[j] = graph->matrix[index][j] + min;
                P[j] = index;
            }
        }
    }
        
    for(i = 0; i < graph->Nv; i++) {
        printf("%d -> %d : %d\n", n, i, cost[i]);
        p = i;
        while(p != n) {
            printf("%d <- ", p);
            p = P[p];
        }
        printf("%d\n\n", p);
    }
    
    return OK;
}
           

二. Floyd算法

1. 定義：

Floyd-Warshall算法（Floyd-Warshall algorithm）是解決任意兩點間的最短路徑的一種算法，可以正确處理有向圖或負權的最短路徑問題，同時也被用于計算有向圖的傳

遞閉包。Floyd-Warshall算法的時間複雜度為O(N3)，空間複雜度為O(N2)。

用于解決多源最短路徑問題。

2. 算法描述：

Floyd算法是一個經典的動态規劃算法。用通俗的語言來描述的話，首先我們的目标是尋找從點i到點j的最短路徑。從動态規劃的角度看問題，我們需要為這個目标重新做一

個诠釋（這個诠釋正是動态規劃最富創造力的精華所在）

      從任意節點i到任意節點j的最短路徑不外乎2種可能，1是直接從i到j，2是從i經過若幹個節點k到j。是以，我們假設Dis(i,j)為節點u到節點v的最短路徑的距離，對于每一個節

點k，我們檢查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，證明從i到k再到j的路徑比i直接到j的路徑短，我們便設定Dis(i,j) = Dis(i,k) + Dis(k,j)，這樣一來，當我們周遊完所

有節點k，Dis(i,j)中記錄的便是i到j的最短路徑的距離。

原理請參考部落格：坐在馬桶上看算法：隻有五行的Floyd最短路算法  http://developer.51cto.com/art/201403/433874.htm

3. 代碼實作：

/* 最短路徑算法Floyd算法 */
Status Floyd(MGraph graph)
{
    int i, j, k, p;
    int A[MaxVertexSize][MaxVertexSize];
    int P[MaxVertexSize][MaxVertexSize];
    
    if(!graph)
        return ERROR;
        
    for(i = 0; i < graph->Nv; i++)
        for(j = 0; j < graph->Nv; j++) {
            A[i][j] = graph->matrix[i][j];
            P[i][j] = j;
        }
        
    for(k = 0; k < graph->Nv; k++)
        for(i = 0; i < graph->Nv; i++)
            for(j = 0; j < graph->Nv; j++)
                if(A[i][k] + A[k][j] < A[i][j]) {
                    A[i][j] = A[i][k] + A[k][j];
                    P[i][j] = P[i][k];
                }
                
    for(i = 0; i < graph->Nv; i++) {
        for(j = 0; j < graph->Nv; j++) {
            printf("%d -> %d : [%d]\n", i, j, A[i][j]);
            p = i;
            while(p != j) {
                printf("%d -> ", p);
                p = P[p][j];
            }
            printf("%d\n", j);
        }
        printf("\n");
    }
    
    return OK;
}