首页 > 上网技巧 > 电脑小技巧 > golang多源最短路径经典算法-Floyd算法

golang多源最短路径经典算法-Floyd算法

时间:2021-06-14 23:16 作者:QQ地带 我要评论

 Floyd算法解决图任意两点间的最短路径问题,允许出现负权的边,但是不允许负权的边组成回路。

基本思想:使用n × n n\times{n}n×n矩阵表示两点间的距离,只有通过引入第三点才能带来改变,如s[i,j]两点引入k点,s[i,j]两点的距离可以使用s[i,k]+s[k,j]之和来替代。当依次引入图中的所有点之后,矩阵标识的距离就是图中任意两点之间最短路径。
 
package main
 
import "fmt"
 
//FMap is used to store point`s distrance
var FMap [4][4]int32
 
//PointNum is point num
var PointNum int = 4
 
func main() {
var Inf int32
Inf = 1 << 16
initMap(Inf)
//中间点
for k := 0; k < PointNum; k++ {
//任意两点间距离更新
for i := 0; i < PointNum; i++ {
for j := 0; j < PointNum; j++ {
if i == j {
continue
}
if FMap[i][j] > FMap[i][k]+FMap[k][j] {
FMap[i][j] = FMap[i][k] + FMap[k][j]
}
}
}
}
fmt.Println(FMap)
}
 
//init map
func initMap(inf int32) {
FMap[0][0] = 0
FMap[0][1] = 2
FMap[0][2] = 6
FMap[0][3] = 4
FMap[1][0] = inf
FMap[1][1] = 0
FMap[1][2] = 3
FMap[1][3] = inf
FMap[2][0] = 7
FMap[2][1] = inf
FMap[2][2] = 0
FMap[2][3] = 1
FMap[3][0] = 5
FMap[3][1] = inf
FMap[3][2] = 12
FMap[3][3] = 0
}
 
 

标签: 算法 golang
顶一下
(0)
0%
踩一下
(0)
0%

Google提供的广告