最短路径Floyd算法

单源最短路径弗洛伊德（Floyd）算法，用于求解图结构中各顶点之间的最短路径

1. 图文解析

已知邻接矩阵G，存在两个二维辅助数组Dist【】【】和Path【】【】
（1）Dist【】【】二维数组用于存储两顶点之间最短距离
（2）Path【】【】二维数组用于存储两顶点最短路径需要经过的上一个顶点下标

最短路径求解过程如下：
（1）初始状态如下
Dist【i】【j】二维数组初始的是图G每条边(i->j)的权值，即相当于邻接矩阵的拷贝
Path【i】【j】二维数组初始均为j，代表顶点i到顶点j的最短路径默认未经过其他顶点

>（2）从第一个顶点A开始作为中间顶点，遍历邻接矩阵的所有边：

1. 比较【i->j】 和 【i->A->j】两条路径的距离，选择更短的一条路径，更新Dist中对应（i，j）的最短距离
2. 同时、如果通过中间顶点的路径更短，则更新Path中对应一对顶点的前驱顶点下标为中间顶点

例如当C作为中间顶点时，A->C->D比A->D的距离更短，则修改对应Dist【0】【3】= 10 + 50 = 60，同时修改对应Path【0】【3】 = Path【0】【2】= 2，即代表A->D最短路径需要经过顶点A->C的最短路径

（3）依次将A、B、C、D、E、F作为中间顶点，最终得到的两个数组结果如下：

（4）分析结果，例如求A->F的最短路径，则有如下过程
A->F，Path【0】【5】= 4，前驱顶点指向中间顶点E；
E->F，Path【4】【5】= 3，前驱顶点指向中间顶点D；
D->F，Path【3】【5】= 5，即D到F没有前驱顶点，直通最短；
即可得出最短路径为A->E->D->F，最短距离 = Dist【0】【5】= 60

2. 源代码

#include<stdio.h>
#include<stdlib.h>
#define MaxVex 10
#define INF 65535

typedef char VertexType;    // 顶点的数据类型
typedef int EdgeType;       // 边的数据类型
typedef struct
{
    VertexType *vertexs;    // 一维数组存放顶点数据
    EdgeType **edges;       // 二维数组存放边的数据
    int numVertexs, numEdges;//顶点数、边数
}AMGraph;

// 初始化领接矩阵
void InitAMGraph(AMGraph *G)
{
    // 初始化顶点和边的数量
    G->numVertexs = 0;
    G->numEdges = 0;
    // 初始化顶点一维数组
    G->vertexs = (VertexType *)malloc(MaxVex*sizeof(VertexType));
    // 初始化边的二维数组
    int i, j;
    G->edges = (EdgeType **)malloc(MaxVex*sizeof(EdgeType *));
    for (i = 0; i < MaxVex; i++)
    {
        G->edges[i] = (EdgeType *)malloc(MaxVex*sizeof(EdgeType));
        // 初始化每条边都为INF（无穷大）
        for ( j = 0; j < MaxVex; j++)
        {
            if (i == j)
            {
                G->edges[i][j] = 0;     // 对角线初始位为0
            }
            else
            {
                G->edges[i][j] = INF;   // 初始化为无穷大
            }
        }
    }
    
    printf("已初始化邻接矩阵!\n");
}   

// 创建领接矩阵
void CreateAMGraph(AMGraph *G)
{
    printf("请输入顶点数和边数:");
    scanf("%d %d", &G->numVertexs, &G->numEdges);

    int i, j, k, weight;
    // 输入顶点数据
    for (i = 0; i < G->numVertexs; i++)
    {
        fflush(stdin);
        printf("请输入第%d个顶点数据:", i + 1);
        scanf("%c", &G->vertexs[i]);
    }
    // 输入边的权值
    for (k = 0; k < G->numEdges; k++)
    {
        printf("请输入第%d条边的两顶点及其权值:", k + 1);
        scanf("%d %d %d", &i, &j, &weight);
        G->edges[i - 1][j - 1] = weight;
    }
    printf("已完成邻接矩阵的创建!\n");
}

// 打印结果
void Display(AMGraph G, EdgeType Dist[][MaxVex], int Path[][MaxVex])
{
    int i, j;
    printf("最短路径长度矩阵:\n");
    printf("\t");
    for (i = 0; i < G.numVertexs; i++)
    {
        printf("%c\t", G.vertexs[i]);
    }
    printf("\n");
    for (i = 0; i < G.numVertexs; i++)
    {
        printf("%c\t", G.vertexs[i]);
        for ( j = 0; j < G.numVertexs; j++)
        {
            if (Dist[i][j] == INF)
            {
                printf("∞\t");
            }
            else
            {
                printf("%d\t", Dist[i][j]);
            }
        }
        printf("\n");
    }
    printf("最短路径矩阵:\n");
    printf("\t");
    for (i = 0; i < G.numVertexs; i++)
    {
        printf("%c\t", G.vertexs[i]);
    }
    printf("\n");
    for (i = 0; i < G.numVertexs; i++)
    {
        printf("%c\t", G.vertexs[i]);
        for (j = 0; j < G.numVertexs; j++)
        {
            if (Path[i][j] != j)
            {
                printf("%c\t", G.vertexs[Path[i][j]]);
            }
            else
            {
                printf("-\t");
            }
        }
        printf("\n");
    }
}

// Floyd算法
void ShortestPath_Floyd(AMGraph G)
{
    int Path[MaxVex][MaxVex];
    EdgeType Dist[MaxVex][MaxVex]; 
    
    int i, j, k, temp;
    for (i = 0; i < G.numVertexs; i++)
    {
        for (j = 0; j < G.numVertexs; j++)
        {
            // 顶点（i）到顶点（j）的前驱顶点初始化为j
            Path[i][j] = j; 
            // 顶点（i）到顶点（j）的距离初始化为边的距离
            Dist[i][j] = G.edges[i][j];
        }
    }
    
    // Floyd算法， 起始顶点（i）、中间顶点（k）、目标顶点（j）
    for (k = 0; k < G.numVertexs; k++)
    {
        for (i = 0; i < G.numVertexs; i++)
        {
            for (j = 0; j < G.numVertexs; j++)
            {
                // 获取顶点（i）经过顶点（k）到达顶点（k）的距离
                if (Dist[i][k] == INF || Dist[k][j] == INF)
                {
                    temp = INF;
                }
                else
                {
                    temp = Dist[i][k] + Dist[k][j];
                }
                // 比较顶点（i->j） 和 （i->k-j） 两条路径的距离
                if (Dist[i][j] > temp)
                {
                    // 如果（i->k->j）距离更短，则更新为最短距离
                    Dist[i][j] = temp;
                    // 并修改（i->j）的前驱中间顶点为顶点（i->k）的前驱中间顶点
                    Path[i][j] = Path[i][k];
                }
                
            }   
        }
        // Display(G, Dist, Path);
    }

    // 输出结果
    Display(G, Dist, Path);
}

int main()
{
    AMGraph G;
    InitAMGraph(&G);
    CreateAMGraph(&G);
    ShortestPath_Floyd(G);
    system("pause");
    return 0;
}

3. 测试结果

#测试用例
6 8
A
B
C
D
E
F
1 3 10
1 5 30
1 6 100
2 3 5
3 4 50
4 6 10
5 4 20
5 6 60