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)
}
}
結果
