【经典算法实现 38】图的最短路径计算（Floyd弗洛伊德算法）
程序员文章站
2024-03-17 10:10:16
...
【经典算法实现 38】图的最短路径计算（Floyd弗洛伊德算法）
本文接着前面的文章，继续探讨最短路径的问题
《【经典算法实现 36】图的最短路径计算（广度优先遍历法 和 深度优先遍历法）》
《【经典算法实现 37】图的最短路径计算（Dijkstra迪杰斯特拉算法 及 其优化）》
今天，我们来看下，别一种计算最短路径的算法：Floyd弗洛伊德算法。
老样子，先上图：
一、Floyd弗洛伊德算法
1. 算法思路
- 如果不使用任何中转，所有结节，各自之间的跟离如下，当前各能够到达的节点的距离都是直接，直线最短：
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | ∞ | 5 | 1 | ∞ | ∞ | ∞ | ∞ |
| B | 5 | ∞ | ∞ | 1 | ∞ | ∞ | ∞ |
| C | ∞ | ∞ | ∞ | 3 | ∞ | ∞ | ∞ |
| D | ∞ | ∞ | ∞ | ∞ | 6 | 4 | ∞ |
| E | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 1 |
| F | ∞ | ∞ | 2 | ∞ | ∞ | ∞ | ∞ |
| G | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
- 当添加中转节点A 时，本来
B->C是不可能的，现在B->C = B->A + A->C = 6，更新表格如下：
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | ∞ | 5 | 1 | ∞ | ∞ | ∞ | ∞ |
| B | 5 | ∞ | ∞ | 1 | ∞ | ∞ | ∞ |
| C | ∞ | 6 | ∞ | 3 | ∞ | ∞ | ∞ |
| D | ∞ | ∞ | ∞ | ∞ | 6 | 4 | ∞ |
| E | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 1 |
| F | ∞ | ∞ | 2 | ∞ | ∞ | ∞ | ∞ |
| G | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
- 当添加中转节点B 时，本来
A->D是不可能的，现在A->D = A->B + B->D = 6，更新表格如下：
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | ∞ | 5 | 1 | 6 | ∞ | ∞ | ∞ |
| B | 5 | ∞ | ∞ | 1 | ∞ | ∞ | ∞ |
| C | ∞ | 6 | ∞ | 3 | ∞ | ∞ | ∞ |
| D | ∞ | ∞ | ∞ | ∞ | 6 | 4 | ∞ |
| E | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 1 |
| F | ∞ | ∞ | 2 | ∞ | ∞ | ∞ | ∞ |
| G | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
- 当添加中转节点C 时，
A->D = A->C + C->D = 4<A->B->D=6，更新A->D的值为6，同理F->D = F->C + C->D = 5，更新表格如下：
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | ∞ | 5 | 1 | 4 | ∞ | ∞ | ∞ |
| B | 5 | ∞ | ∞ | 1 | ∞ | ∞ | ∞ |
| C | ∞ | 6 | ∞ | 3 | ∞ | ∞ | ∞ |
| D | ∞ | ∞ | ∞ | ∞ | 6 | 4 | ∞ |
| E | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 1 |
| F | ∞ | ∞ | 2 | 5 | ∞ | ∞ | ∞ |
| G | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
- 当添加中转节点D 时，多了如下路径
A->E = A->D + D->E = A->C + C->D + D->E = 10A->F = A->D + D->F = A->C + C->D + D->F = 8B->E = B->D + D->E = 7B->F = B->D + D->F = 5C->E = C->D + D->E = 9C->F = C->D + D->F = 7F->E = F->D + D->E = 11
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | - | 5 | 1 | 4 | 10 | 8 | - |
| B | 5 | - | 6 | 1 | 7 | 5 | - |
| C | - | - | - | 3 | 9 | 7 | - |
| D | - | - | - | - | 6 | 4 | - |
| E | - | - | - | - | - | - | 1 |
| F | - | - | 2 | 5 | 11 | - | - |
| G | - | - | - | - | - | - | - |
- 当添加中转节点E 时
A->G = A->E + E->G = A->C + C->D + D->E + E->G = 11B->G = B->E + E->G = B->D + D->E + E->G = 8C->G = C->E + E->G = C->D + D->E + E->G = 10D->G = D->E + E->G = 7F->G = F->E + E->G = F->D + D->E + E->G = 12
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | - | 5 | 1 | 4 | 10 | 8 | 11 |
| B | 5 | - | 6 | 1 | 7 | 5 | 8 |
| C | - | - | - | 3 | 9 | 7 | 10 |
| D | - | - | - | - | 6 | 4 | 7 |
| E | - | - | - | - | - | - | 1 |
| F | - | - | 2 | 5 | 11 | - | 12 |
| G | - | - | - | - | - | - | - |
- 当添加中转节点F 时，
D->C = D->F + F->C = 6
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | - | 5 | 1 | 4 | 10 | 8 | 11 |
| B | 5 | - | 6 | 1 | 7 | 5 | 8 |
| C | - | - | - | 3 | 9 | 7 | 10 |
| D | - | - | 6 | - | 6 | 4 | 7 |
| E | - | - | - | - | - | - | 1 |
| F | - | - | 2 | 5 | 11 | - | 12 |
| G | - | - | - | - | - | - | - |
- 当添加中转节点G 时，由于G不能到任何节点，所以它没法成为中转，最终结果如下；
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | - | 5 | 1 | 4 | 10 | 8 | 11 |
| B | 5 | - | 6 | 1 | 7 | 5 | 8 |
| C | - | - | - | 3 | 9 | 7 | 10 |
| D | - | - | 6 | - | 6 | 4 | 7 |
| E | - | - | - | - | - | - | 1 |
| F | - | - | 2 | 5 | 11 | - | 12 |
| G | - | - | - | - | - | - | - |
好，根据前面的思路，开始写算法吧：
2. Floyd 算法核心代码
void floyd()
{
int i, j, k;
for(i = 0; i<Node_Num; i++){
// 以 i 作为中转，更新所有节点,比如 j->k = j->i + i->k
for(j = 0; j<Node_Num; j++)
for(k = 0; k<Node_Num; k++)
{
if( !(sNode[j][i] == -1 || sNode[i][k] == -1 || j==k) )
if(sNode[j][k] == -1 || sNode[j][i] + sNode[i][k] < sNode[j][k] ){
sNode[j][k] = sNode[j][i] + sNode[i][k];
printf("%c->%c = %c->%c + %c->%c = %d\n", j+'A', k+'A', j+'A' ,i+'A', i+'A', k+'A', sNode[j][k]);
}
}
printf("以%c 为中转时，更新表格数据：\n", i+'A');
Print_Matrix();
}
}
运行结果如下：表格中的所有存在的值，都是两点之间的最短距离。
A B C D E F G
A - 5 1 4 10 8 11
B 5 - 6 1 7 5 8
C - - - 3 9 7 10
D - - 6 - 6 4 7
E - - - - - - 1
F - - 2 5 11 - 12
G - - - - - - -
二、完整代码如下：
#include <stdio.h>
#define Node_Num 7 // 顶点的数量
char pNode[Node_Num]={'A', 'B', 'C', 'D', 'E', 'F', 'G'}; // 用于保存顶点的值
unsigned int sNode[Node_Num][Node_Num]; // 用于表示各边的关系
#define INT_MAX 32767
#define sNode_Num 9 // 9条边
const int s_char[sNode_Num][3]={
{'A','B', 5}, {'A','C', 1},
{'B','D', 1}, {'B','A', 5},
{'C','D', 3},
{'D','E', 6}, {'D','F', 4},
{'E','G', 1},
{'F','C', 2}};
void Print_Matrix(void)
{
int start,end;
printf(" ");
for(start = 0; start<Node_Num; start++)
printf("%c ", pNode[start]);
for(start = 0; start<Node_Num; start++){
printf("\n%c ", pNode[start]);
for(end = 0; end<Node_Num; end++){
if(sNode[start][end] == -1)
printf(" - ");
else
printf("%2d ", sNode[start][end]);
}
}
printf("\n\n");
}
void Create_Matrix()
{
int i = 0, start, end;
memset(sNode, INT_MAX, sizeof(sNode)); //初始化所有边为最大
for(i = 0; i<sNode_Num; i++){
// 获取当前边的起始点
start = s_char[i][0] - 'A';
end = s_char[i][1] - 'A';
sNode[start][end] = s_char[i][2];
}
printf("网矩阵创建完毕\n\n");
}
void floyd()
{
int i, j, k;
for(i = 0; i<Node_Num; i++){
// 以 i 作为中转，更新所有节点,比如 j->k = j->i + i->k
for(j = 0; j<Node_Num; j++)
for(k = 0; k<Node_Num; k++)
{
if( !(sNode[j][i] == -1 || sNode[i][k] == -1 || j==k) )
if(sNode[j][k] == -1 || sNode[j][i] + sNode[i][k] < sNode[j][k] ){
sNode[j][k] = sNode[j][i] + sNode[i][k];
printf("%c->%c = %c->%c + %c->%c = %d\n", j+'A', k+'A', j+'A' ,i+'A', i+'A', k+'A', sNode[j][k]);
}
}
printf("以%c 为中转时，更新表格数据：\n", i+'A');
Print_Matrix();
}
}
int main()
{
// 创建网矩阵
Create_Matrix();
// 打印网矩阵
Print_Matrix();
floyd();
//Print_Matrix();
printf("\n\n");
return 0;
}
2.1 运行结果
网矩阵创建完毕
A B C D E F G
A - 5 1 - - - -
B 5 - - 1 - - -
C - - - 3 - - -
D - - - - 6 4 -
E - - - - - - 1
F - - 2 - - - -
G - - - - - - -
B->C = B->A + A->C = 6
以A 为中转时，更新表格数据：
A B C D E F G
A - 5 1 - - - -
B 5 - 6 1 - - -
C - - - 3 - - -
D - - - - 6 4 -
E - - - - - - 1
F - - 2 - - - -
G - - - - - - -
A->D = A->B + B->D = 6
以B 为中转时，更新表格数据：
A B C D E F G
A - 5 1 6 - - -
B 5 - 6 1 - - -
C - - - 3 - - -
D - - - - 6 4 -
E - - - - - - 1
F - - 2 - - - -
G - - - - - - -
A->D = A->C + C->D = 4
F->D = F->C + C->D = 5
以C 为中转时，更新表格数据：
A B C D E F G
A - 5 1 4 - - -
B 5 - 6 1 - - -
C - - - 3 - - -
D - - - - 6 4 -
E - - - - - - 1
F - - 2 5 - - -
G - - - - - - -
A->E = A->D + D->E = 10
A->F = A->D + D->F = 8
B->E = B->D + D->E = 7
B->F = B->D + D->F = 5
C->E = C->D + D->E = 9
C->F = C->D + D->F = 7
F->E = F->D + D->E = 11
以D 为中转时，更新表格数据：
A B C D E F G
A - 5 1 4 10 8 -
B 5 - 6 1 7 5 -
C - - - 3 9 7 -
D - - - - 6 4 -
E - - - - - - 1
F - - 2 5 11 - -
G - - - - - - -
A->G = A->E + E->G = 11
B->G = B->E + E->G = 8
C->G = C->E + E->G = 10
D->G = D->E + E->G = 7
F->G = F->E + E->G = 12
以E 为中转时，更新表格数据：
A B C D E F G
A - 5 1 4 10 8 11
B 5 - 6 1 7 5 8
C - - - 3 9 7 10
D - - - - 6 4 7
E - - - - - - 1
F - - 2 5 11 - 12
G - - - - - - -
D->C = D->F + F->C = 6
以F 为中转时，更新表格数据：
A B C D E F G
A - 5 1 4 10 8 11
B 5 - 6 1 7 5 8
C - - - 3 9 7 10
D - - 6 - 6 4 7
E - - - - - - 1
F - - 2 5 11 - 12
G - - - - - - -
以G 为中转时，更新表格数据：
A B C D E F G
A - 5 1 4 10 8 11
B 5 - 6 1 7 5 8
C - - - 3 9 7 10
D - - 6 - 6 4 7
E - - - - - - 1
F - - 2 5 11 - 12
G - - - - - - -
请按任意键继续. . .
上一篇： Floyd
下一篇： 【笔记】每一对顶点间的最短路径
推荐阅读
-
【经典算法实现 38】图的最短路径计算（Floyd弗洛伊德算法）
-
22、数据结构预算法 - 图 最短路径 弗洛伊德(Floyd)算法
-
数据结构之图--最短路径（弗洛伊德（Floyd）算法）
-
【经典算法实现 39】图的最短路径计算（优化Dijkstra算法支持负权计算 及 负环检测功能）（参考Bellman_Ford算法）
-
算法：通过弗洛伊德(Floyd)算法，求出图中任意两个顶点的最短路径
-
经典算法之Floyd算法（求图中任意一对顶点间的最短路径）
-
狄克斯拉特算法。 适用于，加权有向无环图，且无负权边，的最短路径计算。
-
图的五种求最短路径算法（Dijkstra、堆优化Dijstra、Bellmon-Ford、SPFA、Floyd-Warshall）
-
python实现图的深度优先搜索(DFS)和广度优先搜索(BFS)算法及Dijkstra最短路径应用
-
邻接矩阵prim:php实现图的邻接矩阵及普里姆(prim算法),弗洛伊德(floyd),迪杰斯特拉(dijkstra)算法