最短路径(Floyd)算法

#include <stdio.h>
#include <stdlib.h>

/* Floyd算法 */

#define VNUM 5
#define MV 65536

int P[VNUM][VNUM];
int A[VNUM][VNUM];
int Matrix[VNUM][VNUM] =
{
    {0, 10, MV, 30, 100},
    {MV, 0, 50, MV, MV},
    {MV, MV, 0, MV, 10},
    {MV, MV, 20, 0, 60},
    {MV, MV, MV, MV, 0},
};

void Floyd()         // O(n*n*n)
{
    int i = 0;
    int j = 0;
    int k = 0;
    //初始化
    for(i=0; i<VNUM; i++)
    {
        for(j=0; j<VNUM; j++)
        {
            A[i][j] = Matrix[i][j];
            P[i][j] = j; //保存路径(i---j的路径)
        }
    }
    //不停的中转
    for(i=0; i<VNUM; i++)
    {
        for(j=0; j<VNUM; j++)
        {
            for(k=0; k<VNUM; k++)
            {
            //若是小于原来的值
                if( (A[j][i] + A[i][k]) < A[j][k] )
                {
             //更新A数组
                    A[j][k] = A[j][i] + A[i][k];
                    P[j][k] = P[j][i];//
                }
            }
        }
    }
    //打印
    for(i=0; i<VNUM; i++)
    {
        for(j=0; j<VNUM; j++)
        {
            int p = -1;
            
            printf("%d -> %d: %d ", i, j, A[i][j]);
            
            printf("%d", i);
            
            p = i;
            
            do
            {
                p = P[p][j]; //p到j的下一个顶点
                
                printf(" -> %d", p);
            } while( p != j);
            
            printf(" ");
        }
    }
}

int main(int argc, char *argv[])
{
      Floyd();
    
    return 0;
}

说明:

Floyd最短路径算法只是Dijkstra最短路径算法的加强， 其本质还是递推 。