算法最短路径
该算法,第一次先将V0的节点连接的权值存入shortTablePath,没连接的,用MAXWEIGHT表示. package mainimport (
"fmt"
)
const MAXVEX int = 9
const MAXWEIGHT int = 1000
var shortTablePath = int{MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT}
func main() {
graph := NewGraph()
var TablePathMin int //存放shortTablePath中,未遍历的最小结点的值
var Vx int //存放shortTablePath中,未遍历的最小结点的下标
var isgetPath bool //记录结点是否已经找到v0到vx的最小路径
// 获取v0这一行的权值数组
for v := 0; v < len(graph); v++ {
shortTablePath = graph
}
shortTablePath = 0
isgetPath = true
//遍历v1 ~ v8
for v := 1; v < len(graph); v++ {
TablePathMin = MAXWEIGHT
//找出shortTablePath中,未遍历的最小结点的值
for w := 0; w < len(graph); w++ {
if !isgetPath && shortTablePath < TablePathMin {
Vx = w
TablePathMin = shortTablePath
}
}
isgetPath = true
for j := 0; j < len(graph); j++ {
if !isgetPath && TablePathMin+graph < shortTablePath {
shortTablePath = TablePathMin + graph
}
}
fmt.Println("遍历完V", v, "后:", shortTablePath)
}
//输出
for i := 0; i < len(shortTablePath); i++ {
fmt.Println("V0到V", i, "最小路径:", shortTablePath)
}
}
func NewGraph() int {
var graph int
var v0 = int{0, 1, 5, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT}
var v1 = int{1, 0, 3, 7, 5, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT}
var v2 = int{5, 3, 0, MAXWEIGHT, 1, 7, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT}
var v3 = int{MAXWEIGHT, 7, MAXWEIGHT, 0, 2, MAXWEIGHT, 3, MAXWEIGHT, MAXWEIGHT}
var v4 = int{MAXWEIGHT, 5, 1, 2, 0, 3, 6, 9, MAXWEIGHT}
var v5 = int{MAXWEIGHT, MAXWEIGHT, 7, MAXWEIGHT, 3, 0, MAXWEIGHT, 5, MAXWEIGHT}
var v6 = int{MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, 3, 6, MAXWEIGHT, 0, 2, 7}
var v7 = int{MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, 9, 5, 2, 0, 4}
var v8 = int{MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, 7, 4, 0}
graph = v0
graph = v1
graph = v2
graph = v3
graph = v4
graph = v5
graph = v6
graph = v7
graph = v8
return graph
}
页:
[1]