本文最后更新于 超过 3 年前，文中所描述的信息可能已发生改变。
Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
相关代码
go
func Floyd(data [][]float64) {
n := len(data)
for k := 0; k < n; k++ {
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if data[i][j] > data[i][k]+data[k][j] {
data[i][j] = data[i][k] + data[k][j]
}
}
}
}
}go
import (
"dataStructure/floyd"
"log"
"math"
)
func main() {
data := [][]float64{
{0, 2, 6, 4},
{math.Inf(1), 0, 1, math.Inf(1)},
{7, math.Inf(1), 0, 1},
{5, math.Inf(1), 12, 0},
}
floyd.Floyd(data)
log.Println(data)
}结果
go
2022/01/08 15:51:42 [[0 2 3 4] [7 0 1 2] [6 8 0 1] [5 7 8 0]]