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
|
type Edge struct {
src int
dest int
weight float64
}
type Graph struct {
vertices int
edges []Edge
}
func InitGraph(vertices int) *Graph {
return &Graph{
vertices: vertices,
edges: make([]Edge, 0),
}
}
func (g *Graph) AddEdge(src, dest int, weight float64) {
g.edges = append(g.edges, Edge{src, dest, weight})
}
func BellmanFord(g *Graph, source int) ([]float64, []int) {
dist := make([]float64, g.vertices)
prev := make([]int, g.vertices)
for i := 0; i < g.vertices; i++ {
dist[i] = math.Inf(1) // 将所有节点的距离设为 无穷大
prev[i] = -1 // 保存到节点v最短距离，到v的上一跳是哪个节点
}
dist[source] = 0 // 起点的距离为 0
// Relax edges V - 1 times（i 从 1 开始计数）
for i := 1; i < g.vertices; i++ {
for _, edge := range g.edges {
u := edge.src
v := edge.dest
w := edge.weight
if dist[u]+w < dist[v] {
dist[v] = dist[u] + w
prev[v] = u
}
}
}
// Check for negative cycle，经过了 v-1 次循环了，还是存在更短的路径证明存在负环了
for _, edge := range g.edges {
u := edge.src
v := edge.dest
w := edge.weight
if dist[u]+w < dist[v] {
fmt.Println("Graph contains a negative weight cycle")
return nil, nil
}
}
return dist, prev
}
func PrintShortestPaths(dist []float64, prev []int, source int) {
fmt.Println("Shortest Paths from vertex", source)
for i := 0; i < len(dist); i++ {
if dist[i] == math.Inf(1) {
fmt.Printf("Vertex %d is not reachable\n", i)
} else {
path := []int{}
j := i
for j != -1 {
path = append([]int{j}, path...)
j = prev[j]
}
fmt.Printf("Vertex %d: Distance=%f, Path=%v\n", i, dist[i], path)
}
}
}
func main() {
g := InitGraph(5)
g.AddEdge(0, 1, 1)
g.AddEdge(0, 2, 1)
g.AddEdge(1, 2, 1)
g.AddEdge(1, 3, 1)
g.AddEdge(1, 4, 1)
g.AddEdge(2, 3, 1)
g.AddEdge(2, 4, 1)
g.AddEdge(3, 1, 1)
g.AddEdge(4, 0, 1)
g.AddEdge(4, 3, 1)
source := 0
dist, prev := BellmanFord(g, source)
if dist != nil && prev != nil {
PrintShortestPaths(dist, prev, source)
}
}
|
