Floyd-Marshall最短路径
图
在寻找任意两点间的最短路径时(A->B)，需要引入第三个点(C)，通过第三个点中转，看是否能够使 A->C->B 的距离小于 A->B 的距离。
// 999 表示两点之间不连通
var theMap = [4][4]int{
{0, 2, 6, 4},
{999, 0, 3, 999},
{7, 999, 0, 1},
{5, 999, 12, 0},
}
func Floyd() {
fmt.Println("Floyd")
for point := 0; point < 4; point++ {
for i := 0; i < 4; i++ {
for j := 0; j < 4; j++ {
if theMap[i][j] > (theMap[i][point] + theMap[point][j]) {
theMap[i][j] = theMap[i][point] + theMap[point][j]
}
}
}
fmt.Println(" Cover point()", point, ") ", theMap)
}
}
结果
