本文最后更新于 2022年01月08日 已经是 509天前了 ，文章可能具有时效性，若有错误或已失效，请在下方留言。
Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
相关代码
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]
}
}
}
}
}
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)
}
结果
2022/01/08 15:51:42 [[0 2 3 4] [7 0 1 2] [6 8 0 1] [5 7 8 0]]
