求助关于Floyd算法如何记录某两点最短路径

2025-03-04 12:32:27

推荐回答（1个）

回答1：

path[i][j]表示从顶点i到顶点j的路径上，顶点j的前驱
void floyd(int numVertices) {
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
a[i][j] = weight(i, j);
if (i != j && a[i][j] < MAXNUM) {
path[i][j] = i;
}
else {
path[i][j] = -1;
}
}
}
for (int k = 0; k < numVertices; k++) {
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
if (a[i][k] + a[k][j] < a[i][j]) {
a[i][j] = a[i][k] + a[k][j];
path[i][j] = path[k][j];
}
}
}
}
}

求助关于Floyd算法 如何记录某两点最短路径

求助关于Floyd算法如何记录某两点最短路径