Floyd算法

基本概念

多源最短路,即要求算出图中每两个顶点之间的最短路。一种方法是把n个点分别当成源点用Dijkstra算,时间复杂度是O(n3),优化后也可以变为O(n2logn)。另一种方法就是经典Floyd算法,虽然复杂度是O(n3),但是代码只有4行。Floyd算法本质上是一个动态规划算法。

经典实现

1
2
3
4
5
6
7
8
9
void Floyd(){
for(int k = 1; k <= N; k++){
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
A[i][j] = min(A[i][j], A[i][k] + A[k][j]);
}
}
}
}