/
dijkstra.go
106 lines (88 loc) · 2.14 KB
/
dijkstra.go
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
// Copyright (c) 2014 Flemming Andersen.
// Distributed under the MIT License (MIT)
// which can be found in the LICENSE file.
package dijkstra
import (
"container/heap"
"errors"
)
// Node is an interface for your own implementation of a vertex in a graph.
type Node interface {
Edges() []Edge
}
// Edge is an interface for your own implementation of an edge between two vertices in a graph.
type Edge interface {
Destination() Node
Weight() float64
}
// ShortestPath finds a shortest path between the start and end nodes.
// The two nodes' underlying values must be pointers.
func ShortestPath(start, end Node) ([]Node, error) {
visited := make(map[Node]struct{})
dists := make(map[Node]float64)
prev := make(map[Node]Node)
dists[start] = 0
queue := &queue{&queueItem{value: start, weight: 0, index: 0}}
heap.Init(queue)
for queue.Len() > 0 {
// Done.
if _, ok := visited[end]; ok {
break
}
item := heap.Pop(queue).(*queueItem)
n := item.value
for _, edge := range n.Edges() {
dest := edge.Destination()
dist := dists[n] + edge.Weight()
if tentativeDist, ok := dists[dest]; !ok || dist < tentativeDist {
dists[dest] = dist
prev[dest] = n
heap.Push(queue, &queueItem{value: dest, weight: dist})
}
}
visited[n] = struct{}{}
}
if _, ok := visited[end]; !ok {
return nil, errors.New("no shortest path exists")
}
path := []Node{end}
for next := prev[end]; next != nil; next = prev[next] {
path = append(path, next)
}
// Reverse path.
for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
path[i], path[j] = path[j], path[i]
}
return path, nil
}
type queueItem struct {
value Node
weight float64
index int
}
type queue []*queueItem
func (q queue) Len() int {
return len(q)
}
func (q queue) Less(i, j int) bool {
return q[i].weight < q[j].weight
}
func (q queue) Swap(i, j int) {
q[i], q[j] = q[j], q[i]
q[i].index = i
q[j].index = j
}
func (q *queue) Push(x interface{}) {
n := len(*q)
item := x.(*queueItem)
item.index = n
*q = append(*q, item)
}
func (q *queue) Pop() interface{} {
old := *q
n := len(old)
item := old[n-1]
item.index = -1 // for safety
*q = old[0 : n-1]
return item
}