/
dijkstra.go
91 lines (77 loc) · 2.86 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
package path
import (
"container/heap"
"github.com/natevvv/osm-ship-routing/pkg/graph"
"github.com/natevvv/osm-ship-routing/pkg/queue"
)
type Dijkstra struct {
g graph.Graph
dijkstraItems []*queue.Item
pqPops int
pqUpdates int
relaxationAttempts int
relaxedEdges int
}
func NewDijkstra(g graph.Graph) *Dijkstra {
return &Dijkstra{g: g}
}
func (d *Dijkstra) ComputeShortestPath(origin, destination int) int {
d.dijkstraItems = make([]*queue.Item, d.g.NodeCount())
originItem := queue.NewQueueItem(origin, 0, -1) //{ItemId: origin, Priority: 0, Predecessor: -1, Index: -1}
d.dijkstraItems[origin] = originItem
pq := make(queue.Queue, 0)
heap.Init(&pq)
heap.Push(&pq, d.dijkstraItems[origin])
d.pqPops = 0
d.pqUpdates = 0
d.relaxationAttempts = 0
d.relaxedEdges = 0
for len(pq) > 0 {
currentPqItem := heap.Pop(&pq).(*queue.Item)
currentNodeId := currentPqItem.ItemId
d.pqPops++
for _, arc := range d.g.GetArcsFrom(currentNodeId) {
d.relaxationAttempts++
successor := arc.Destination()
if d.dijkstraItems[successor] == nil {
newPriority := d.dijkstraItems[currentNodeId].Priority + arc.Cost()
pqItem := queue.NewQueueItem(successor, newPriority, currentNodeId) //{ItemId: successor, Priority: newPriority, Predecessor: currentNodeId, Index: -1}
d.dijkstraItems[successor] = pqItem
heap.Push(&pq, pqItem)
d.pqUpdates++
} else {
if updatedDistance := d.dijkstraItems[currentNodeId].Priority + arc.Cost(); updatedDistance < d.dijkstraItems[successor].Priority {
pq.Update(d.dijkstraItems[successor], updatedDistance)
d.pqUpdates++
d.dijkstraItems[successor].Predecessor = currentNodeId
}
}
d.relaxedEdges++
}
if currentNodeId == destination {
break
}
}
length := -1 // by default a non-existing path has length -1
if d.dijkstraItems[destination] != nil {
length = d.dijkstraItems[destination].Priority
}
return length
}
func (d *Dijkstra) GetPath(origin, destination graph.NodeId) []graph.NodeId {
path := make([]graph.NodeId, 0) // by default, a non-existing path is an empty slice
if d.dijkstraItems[destination] != nil {
for nodeId := destination; nodeId != -1; nodeId = d.dijkstraItems[nodeId].Predecessor {
path = append([]int{nodeId}, path...)
}
}
return path
}
func (d *Dijkstra) GetSearchSpace() []*DijkstraItem { panic("not implemented") }
func (d *Dijkstra) GetPqPops() int { return d.pqPops }
func (d *Dijkstra) GetPqUpdates() int { return d.pqUpdates }
func (d *Dijkstra) GetEdgeRelaxations() int { return d.relaxedEdges }
func (d *Dijkstra) GetRelaxationAttempts() int { return d.relaxationAttempts }
func (d *Dijkstra) GetStalledNodesCount() int { return 0 }
func (d *Dijkstra) GetUnstalledNodesCount() int { return 0 }
func (d *Dijkstra) GetGraph() graph.Graph { return d.g }