floyd算法详解

算法是一种用于求解所有顶点对之间的最短路径问题的算法，特别适用于稠密图。下面是一个使用C++实现的算法示例：

#include <iostream>
#include <climits> // For INT_MAXusing namespace std;const int V = 4; // 图的顶点数// 定义一个函数来实现Floyd算法
void floyd(int graph[V][V]) {int dist[V][V];int i, j, k;// 初始化距离矩阵for (i = 0; i < V; i++)for (j = 0; j < V; j++)dist[i][j] = graph[i][j];// 运行Floyd算法for (k = 0; k < V; k++) {// 检查顶点k是否在i到j的路径上for (i = 0; i < V; i++) {for (j = 0; j < V; j++) {if (dist[i][k] + dist[k][j] < dist[i][j])dist[i][j] = dist[i][k] + dist[k][j];}}}// 打印最短路径矩阵cout << "最短路径矩阵:\n";for (i = 0; i < V; i++) {for (j = 0; j < V; j++) {if (dist[i][j] == INT_MAX)cout << "INF ";elsecout << dist[i][j] << " ";}cout << endl;}
}// 主函数
int main() {int graph[V][V] = { {0,   5,  INT_MAX, 10},{INT_MAX, 0,   3,   INT_MAX},{INT_MAX, INT_MAX, 0,   1},{INT_MAX, INT_MAX, INT_MAX, 0} };floyd(graph);return 0;
}

在这个示例中：

1.  定义了图的顶点数。
2.  是一个二维数组，表示顶点之间的边权重，其中 _ 表示两个顶点之间没有直接的边。
3.  函数实现了算法，计算所有顶点对之间的最短路径，并打印结果。

你可以根据实际需要修改  和  的值，以适应不同的图结构。

但是注意：算法的时间复杂度是,可以处理负数边权的问题，所以时间要求一定要看清楚哦！