1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
| package main
import (
"fmt"
)
const MAXVEX int = 9
const MAXWEIGHT int = 1000
var shortestPath = [MAXVEX]int{MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT}
func main() {
graph := NewGraph()
shortestV := make(map[int]int)
var pathMin int
var Vx int
var isgetPath [MAXVEX]bool
for v := 0; v < len(graph); v++ {
shortestPath[v] = graph[0][v]
}
fmt.Println("shortTablePath is:", shortestPath)
isgetPath[0] = true
for v := 1; v < len(graph); v++ {
fmt.Printf("------第%d次大循环开始------\n", v)
pathMin = MAXWEIGHT
for n := 0; n < len(graph); n++ {
fmt.Printf("----第%d次第一个小循环开始----\n", n)
if !isgetPath[n] && shortestPath[n] < pathMin {
fmt.Println("Vx和n是:", Vx, n)
Vx = n
pathMin = shortestPath[n]
fmt.Println("当前的pathMin为:", pathMin)
}
fmt.Printf("~~~~第%d次第一个小循环结束~~~~\n\n", n)
}
isgetPath[Vx] = true
fmt.Println("此时的isgetPath为:", isgetPath)
for n := 0; n < len(graph); n++ {
fmt.Printf("------第%d次第二个小循环开始------\n", n)
fmt.Println("pathMin 和 graph[Vx][n]为", pathMin, graph[Vx][n])
fmt.Println("shortestPath[n]", shortestPath[n])
if !isgetPath[n] && pathMin+graph[Vx][n] < shortestPath[n] {
shortestPath[n] = pathMin + graph[Vx][n]
shortestV[n] = Vx
fmt.Println("shortestPath为:", shortestPath)
fmt.Println("shortestV为:", shortestV)
}
fmt.Printf("~~~~~第%d次第二个小循环结束~~~~~~~\n\n", n)
}
fmt.Println("遍历完V", v, "后:", shortestPath)
fmt.Println("各个节点的前驱节点为", shortestV)
fmt.Printf("~~~~~~~第%d次大循环结束~~~~~~~\n\n", v)
}
for i := 0; i < len(shortestPath); i++ {
fmt.Println("V0到V", i, "最小路径:", shortestPath[i])
}
}
func NewGraph() [MAXVEX][MAXVEX]int {
var graph [MAXVEX][MAXVEX]int
var v0 = [MAXVEX]int{0, 1, 5, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT}
var v1 = [MAXVEX]int{1, 0, 3, 7, 5, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT}
var v2 = [MAXVEX]int{5, 3, 0, MAXWEIGHT, 1, 7, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT}
var v3 = [MAXVEX]int{MAXWEIGHT, 7, MAXWEIGHT, 0, 2, MAXWEIGHT, 3, MAXWEIGHT, MAXWEIGHT}
var v4 = [MAXVEX]int{MAXWEIGHT, 5, 1, 2, 0, 3, 6, 9, MAXWEIGHT}
var v5 = [MAXVEX]int{MAXWEIGHT, MAXWEIGHT, 7, MAXWEIGHT, 3, 0, MAXWEIGHT, 5, MAXWEIGHT}
var v6 = [MAXVEX]int{MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, 3, 6, MAXWEIGHT, 0, 2, 7}
var v7 = [MAXVEX]int{MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, 9, 5, 2, 0, 4}
var v8 = [MAXVEX]int{MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, 7, 4, 0}
graph[0] = v0
graph[1] = v1
graph[2] = v2
graph[3] = v3
graph[4] = v4
graph[5] = v5
graph[6] = v6
graph[7] = v7
graph[8] = v8
return graph
}
|
