数据结构_最短路径Floyd算法(C语言)_c语言弗洛伊德法求最短路径

最短路径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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16