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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
// Copyright 2011 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// Simple demonstration of a graph interface and
// Dijkstra's algorithm built on top of that interface,
// without using inheritance.
package graph
import "container/heap"
// A Graph is the interface implemented by graphs that
// this package can run algorithms on.
type Graph interface {
// NumVertex returns the number of vertices in the graph.
NumVertex() int
// VertexID returns a vertex ID, 0 <= ID < NumVertex(), for v.
VertexID(v Vertex) int
// Neighbors returns a slice of vertices that are adjacent
// to v in the graph.
Neighbors(v Vertex) []Vertex
}
type Vertex interface {
String() string
}
// ShortestPath uses Dijkstra's algorithm to find the shortest
// path from start to end in g. It returns the path as a slice of
// vertices, with start first and end last. If there is no path,
// ShortestPath returns nil.
func ShortestPath(g Graph, start, end Vertex) []Vertex {
d := newDijkstra(g)
d.visit(start, 1, nil)
for !d.empty() {
p := d.next()
if g.VertexID(p.v) == g.VertexID(end) {
break
}
for _, v := range g.Neighbors(p.v) {
d.visit(v, p.depth+1, p)
}
}
p := d.pos(end)
if p.depth == 0 {
// unvisited - no path
return nil
}
path := make([]Vertex, p.depth)
for ; p != nil; p = p.parent {
path[p.depth-1] = p.v
}
return path
}
// A dpos is a position in the Dijkstra traversal.
type dpos struct {
depth int
heapIndex int
v Vertex
parent *dpos
}
// A dijkstra is the Dijkstra traversal's work state.
// It contains the heap queue and per-vertex information.
type dijkstra struct {
g Graph
q []*dpos
byID []dpos
}
func newDijkstra(g Graph) *dijkstra {
d := &dijkstra{g: g}
d.byID = make([]dpos, g.NumVertex())
return d
}
func (d *dijkstra) pos(v Vertex) *dpos {
p := &d.byID[d.g.VertexID(v)]
p.v = v // in case this is the first time we've seen it
return p
}
func (d *dijkstra) visit(v Vertex, depth int, parent *dpos) {
p := d.pos(v)
if p.depth == 0 {
p.parent = parent
p.depth = depth
heap.Push(d, p)
}
}
func (d *dijkstra) empty() bool {
return len(d.q) == 0
}
func (d *dijkstra) next() *dpos {
return heap.Pop(d).(*dpos)
}
// Implementation of heap.Interface
func (d *dijkstra) Len() int {
return len(d.q)
}
func (d *dijkstra) Less(i, j int) bool {
return d.q[i].depth < d.q[j].depth
}
func (d *dijkstra) Swap(i, j int) {
d.q[i], d.q[j] = d.q[j], d.q[i]
d.q[i].heapIndex = i
d.q[j].heapIndex = j
}
func (d *dijkstra) Push(x interface{}) {
p := x.(*dpos)
p.heapIndex = len(d.q)
d.q = append(d.q, p)
}
func (d *dijkstra) Pop() interface{} {
n := len(d.q)
x := d.q[n-1]
d.q = d.q[:n-1]
x.heapIndex = -1
return x
}
|
