所有顶点间最短路径——Floyd算法

算法思想及数据结构

  Floyd算法的基本思想是，把初始直接相连的通路中，把图中的每一个节点都尝试加入到各对点的通路当中，尝试是否能够得到更短的通路。若是，则保留这个通路，如此整个图中的点之间的通路距离就会在遍历中保持缩减的趋势最终达到最优。

arsc [][]int //图的邻接矩阵
由于递推的过程可直接对邻接矩阵做处理，因此不需要其他的辅助元素。

算法流程

1. x = 0，对于所有顶点arsc[i][j]，若存在arsc[i][j] > arsc[i][x] + arsc[x][j]，则更新arsc[i][j]。
2. x自增，循环n次。

算法复杂度

$O(|V|^3) $
同等的复杂度下可以对每个顶点使用dijskra算法达到同样的效果。

算法实现

package main

import "fmt"

// emmmmm，就是一个三重循环就结束了
// 由于代码紧凑，操作简单，虽然floyd算法的时间复杂度很高，但对于中型的图还是效率很高的。
func floyd(arsc [][]int) [][]int {
	n := len(arsc)
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			for k := 0; k < n; k++ {
				if arsc[j][k] > arsc[j][i]+arsc[i][k] {
					arsc[j][k] = arsc[j][i] + arsc[i][k]
				}
			}
		}
	}
	return arsc
}

func main() {
	arsc := [][]int{
		{0, 5, 0, 7},
		{0, 0, 4, 2},
		{3, 3, 0, 2},
		{0, 0, 1, 0},
	}
	fmt.Println(floyd(arsc))
}