多源點最短路徑-弗洛伊德算法(Floyd)

求所有頂點到所有頂點的最短路徑，而迪杰斯特拉是求單源點到所有頂點的最短路徑。

幾個用到的變量和數組的含義:

• 變量k：中轉頂點坐標
• 數組P：存放頂點之間的中轉結點的數組，比如：

P[1][4] = 2;//頂點1到頂點4途徑頂點2
P[2][4] = 3;//頂點2到頂點4又途徑頂點3
P[3][4] = 4;//頂點3到頂點4經過頂點4，即表明3->4之間無中轉頂點了。

• 從而得：

  當P[v][k] == k的時候，即走到了路徑的最后。

• 數組D：存放了頂點到頂點之間的最小路徑和。

代碼實現：

typedef int ShortPathTable[MAXVEX][MAXVEX]
typedef int PathMatrix[MAXVEX][MAXVEX]
void Floyd(MGraph G, PathMatrix *P, ShortPathTable *D)
{
    int v, w, k; /*k為中轉頂點的下標*/
    for(v = 0; v < G.numVertexes; v++)
    {
        for(w = 0; w < G.numVertexes; w++)
        {
            (*D)[v][w] = G.arc[v][w];
            (*P)[v][w] = w; /*P[v][w] == w 的時候表明,v -> w 之間沒有中轉頂點了，初始化的時候肯定都是沒有中轉頂點的，所以都置為w*/
        }
    }
    /*以上完成了初始化工作*/
    /*注意三層for循環(huán)的次序，k作為中轉頂點在第二層*/
    for(v = 0; v < G.numVertexes; v++)
    {
        for(k = 0; k < G.numVertexes; k++)
        {
            for(w = 0; w < G.numVertexes; w++)
            {
                /*如果頂點v到w的路徑和 大于 頂點v到中轉頂點k的路徑和 + 頂點k到頂點w的路徑和
                  就更新為小者，同時要更新v到w之間經過 [頂點v到頂點k之間的中轉頂點]
                */
                if((*D)[v][w] > ((*D)[v][k] + (*D)[k][w]))
                {
                    (*D)[v][w] = ((*D)[v][k] + (*D)[k][w]);
                    (*P)[v][w] = (*P)[v][k];/*路徑設置為經過下標為k的頂點*/
                }
            }
        }
    }



    /*根據P數組打印路徑的算法*/
    for(v = 0; v < G.numVertexes; v++)
    {
        for(w = v+1; w < G.numVertexes; w++)
        {
            printf("v%d-v%d weight: %d", v, w, (*D)[v][w]);
            k = (*P)[v][w]; /*獲得第一個路徑頂點下標*/
            printf(" path: %d": v);/*打印源點*/
            while(k != w)
            {
                printf("-> %d", k);
                k = (*P)[k][w];
            }
        }
        printf(" -> %d\n", w);/*打印終點*/
    }
}