/**
* @Author Dehui Ou
* @Date 15:58 2021/7/20 0020
* @Description Floyd 多源最短路径
*/
#include "iostream"
#define n 5
#define INF 0x3f3f3f3f
using namespace std;
void display(int G[][n], int path[][n]);
void dfs(int path[][n], int i, int j);
/**
* @Algorithm principle
* ：第k次迭代，代表可以从第Vk个结点中转。由于前面已经进行了k - 1次的迭代，故已经考虑到了从V1,V2,...,Vk-1迭代的情形
* ：故对于顶点Vi -> Vj,其中转顶点可能有多个，例如：V0 -> V4 其实是V0 -> V2 -> V1 -> V3 -> V4
* @param G[][] 初始邻接矩阵
* @param path[][] 中转矩阵 path[i][j] = k,代表i ...- > k ...-> j;即i->直接有中转结点k
* @param k 代表允许从第k个结点作为中转
*/
void Floyd(int G[][n], int path[][n]) {
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (G[i][j] > G[i][k] + G[k][j]) {
G[i][j] = G[i][k] + G[k][j];
path[i][j] = k;
}
}
}
}
}
/**
* @Description Floyd测试用例 图Floyd2.jpg
*/
int main() {
int G[][n] = {{0, INF, 1, INF, 10},
{INF, 0, INF, 1, 5},
{INF, 1, 0, INF, 7,},
{INF, INF, INF, 0, 1},
{INF, INF, INF, INF, 0}};
int path[][n] = {{-1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1}};
cout << "------------------- print before_Floyd -------------------" << endl;
display(G, path);
Floyd(G, path);
cout << "------------------- print after_Floyd -------------------" << endl;
display(G, path);
cout << "\t\t\t\t--------- print path ---------\t\t\t\t" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (G[i][j] == INF || G[i][j] == 0) {
continue;
} else {
printf("V%d -> V%d(weight:%d) : V%d", i, j, G[i][j], i);
dfs(path, i, j);
printf("->V%d\n", j);
}
}
}
}
// 中序遍历打印Vi -> Vj路径上的所有结点
/** 原理 :我们知道k = path[i][j] 代表路径i,j直接有中转结点k，表示为i ...->k ...->j;
* 而i ...->k直接同样也可能存在中转结点，且i ...->k的中转结点要先于k输出，故整个过程可看作
* 用划分[i,j]为[i,k],[k,j], 递归的处理完[i,k]后, 输出k顶点，然后递归处理[k,j]，符合左根右的
* 遍历规则，顾可用中序dfs完成对结点的输出。
*/
void dfs(int path[][n], int i, int j) {
// 证明i, j之间有中转结点
if (path[i][j] != -1) {
int k = path[i][j];
dfs(path, i, k);
printf("->V%d", k);
dfs(path, k, j);
} else {
// path[i][j] == -1 说明Vi -> Vj是直接相连的
}
}
// 打印G矩阵与path矩阵
void display(int G[][n], int path[][n]) {
cout << "G[][] :\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (G[i][j] == INF)
cout << "INF" << "\t";
else
cout << G[i][j] << "\t";
}
cout << endl;
}
cout << "\nPath[][] :\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << path[i][j] << "\t";
}
cout << endl;
}
}
测试用例图示如下
程序输出如下
------------------- print before_Floyd -------------------
G[][] :
0 INF 1 INF 10
INF 0 INF 1 5
INF 1 0 INF 7
INF INF INF 0 1
INF INF INF INF 0
Path[][] :
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
------------------- print after_Floyd -------------------
G[][] :
0 2 1 3 4
INF 0 INF 1 2
INF 1 0 2 3
INF INF INF 0 1
INF INF INF INF 0
Path[][] :
-1 2 -1 2 3
-1 -1 -1 -1 3
-1 -1 -1 1 3
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
--------- print path ---------
V0 -> V1(weight:2) : V0->V2->V1
V0 -> V2(weight:1) : V0->V2
V0 -> V3(weight:3) : V0->V2->V1->V3
V0 -> V4(weight:4) : V0->V2->V1->V3->V4
V1 -> V3(weight:1) : V1->V3
V1 -> V4(weight:2) : V1->V3->V4
V2 -> V1(weight:1) : V2->V1
V2 -> V3(weight:2) : V2->V1->V3
V2 -> V4(weight:3) : V2->V1->V3->V4
V3 -> V4(weight:1) : V3->V4
Process finished with exit code 0