80 lines
2.2 KiB
C++
80 lines
2.2 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
// 最大支持10*10的二维表，即10个节点以内的都支持
|
||
#define N 10
|
||
|
||
// 弗洛伊德（Floyd）算法求图的最短路径
|
||
// https://blog.csdn.net/jeffleo/article/details/53349825
|
||
|
||
int vexnum;//顶点数
|
||
int path[N][N];//记录对应点的最小路径的前驱点，例如p(1,3) = 2 说明顶点1到顶点3的最小路径要经过2
|
||
int dist[N][N];//记录顶点间的最小路径值
|
||
|
||
int main() {
|
||
//输入+输出重定向
|
||
freopen("../MiniPath/Floyd.txt", "r", stdin);
|
||
|
||
//读入数据输入
|
||
cin >> vexnum; //端点数
|
||
//二维邻接矩阵
|
||
for (int i = 0; i < vexnum; i++) {
|
||
for (int j = 0; j < vexnum; j++) {
|
||
//读入原始数据
|
||
cin >> dist[i][j];
|
||
//感觉这句有些废话的意思~
|
||
path[i][j] = j;
|
||
}
|
||
}
|
||
//这里是弗洛伊德算法的核心部分
|
||
//k为中间点
|
||
for (int k = 0; k < vexnum; k++) {
|
||
//i为起点
|
||
for (int i = 0; i < vexnum; i++) {
|
||
//j为终点
|
||
for (int j = 0; j < vexnum; j++) {
|
||
if (dist[i][j] > (dist[i][k] + dist[k][j])) {
|
||
dist[i][j] = dist[i][k] + dist[k][j]; //更新最小路径
|
||
//标记是通过哪个节点进行中转的,更新最小路径中间顶点
|
||
path[i][j] = path[i][k];
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
printf("\ndist矩阵\n");
|
||
for (int i = 0; i < vexnum; i++) {
|
||
for (int j = 0; j < vexnum; j++) {
|
||
printf("%d ", dist[i][j]);
|
||
}
|
||
printf("\n");
|
||
}
|
||
|
||
printf("\npath矩阵\n");
|
||
for (int i = 0; i < vexnum; i++) {
|
||
for (int j = 0; j < vexnum; j++) {
|
||
printf("%d ", path[i][j]);
|
||
}
|
||
printf("\n");
|
||
}
|
||
|
||
//求 0 到 3的最小路径
|
||
int i = 0;
|
||
int j = 3;
|
||
|
||
printf("\n%d -> %d 的最小路径为：%d\n", i, j, dist[i][j]);
|
||
|
||
//正向推出是怎么来的这个数
|
||
int k = path[i][j];
|
||
printf("path: %d", i);//打印起点
|
||
while (k != j) {
|
||
printf("-> %d", k);//打印中间点
|
||
k = path[k][j];
|
||
}
|
||
printf("-> %d\n", j);
|
||
|
||
//关闭文件
|
||
fclose(stdin);
|
||
}
|