Floyd算法可以用来求最长路径吗

Floyd算法可以用来求最长路径吗

有环图不存在最长路径吧?因为可以无限绕圈
如果是无环图的话,把所有边取相反数,就变成了求最短路,可以使用floyd,因为两点之间最多只有一条路相通

#include <stdio.h> #define n 7 #define i 999 int graph[n][n] = { {i, 4, 5, 8, i, i, i}, {i, i, i, 6, 6, i, i}, {i, i, i, 5, i, 7, i}, {i, i, i, i, 8, 9, 9}, {i, i, i, i, i, i, 5}, {i, i, i, i, i, i, 4}, {i, i, i, i, i, i, i} }; int list[n]; int topologicalorder(); void main() { int i, j, k, l; int ee[n], el[n]; int path_e[n][n], path_l[n][n], n_e[n], n_l[n]; for (i = 0; i < n; i++) { n_e[i] = 0; n_l[i] = 0; ee[i] = i; el[i] = 0; } ee[0] = el[0] = 0; path_e[0][0] = 0; path_l[0][0] = 0; n_e[0] = 1; n_l[0] = 1; if (!topologicalorder()) return; for (i = 0; i < n; i++) { k = list[i]; for (j = 0; j < n; j++) { if (graph[k][j] != i) { if (graph[k][j] + ee[k] < ee[j]) { ee[j] = graph[k][j] + ee[k]; for (l = 0; l < n_e[k]; l++) { path_e[j][l] = path_e[k][l]; } path_e[j][l] = j; n_e[j] = l + 1; } if (graph[k][j] + el[k] > el[j]) { el[j] = graph[k][j] + el[k]; for (l = 0; l < n_l[k]; l++) { path_l[j][l] = path_l[k][l]; } path_l[j][l] = j; n_l[j] = l + 1; } } } } for (i = 0; i < n; i++) { printf("shortest(%d): %2d path: ", i + 1, ee[i]); for (j = 0; j < n_e[i]; j++) { printf("%d ", path_e[i][j] + 1); } printf("\n"); printf("longest (%d): %2d path: ", i + 1, el[i]); for (j = 0; j < n_l[i]; j++) { printf("%d ", path_l[i][j] + 1); } printf("\n"); } } int topologicalorder() { int i, j, top, count; int indegree[n], stack[n]; top = 0; for (i = 0; i < n; i++) { indegree[i] = 0; for (j = 0; j < n; j++) { if (graph[j][i] != i) { indegree[i]++; } } if (!indegree[i]){ stack[top++] = i; } } count = 0; while (top != 0) { i = stack[--top]; list[count++] = i; for (j = 0; j < n; j++) { if (graph[i][j] != i) { if (!(--indegree[j])) { stack[top++] = j; } } } } return (count < n) ? 0 : 1; }