forked from shellfly/algo
-
Notifications
You must be signed in to change notification settings - Fork 0
/
dijkstra_sp.go
69 lines (58 loc) · 1.37 KB
/
dijkstra_sp.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
package algs4
// PositiveInfinity is a fake positive infinity value
const PositiveInfinity = 999999.0
// DijkstraSP ...
type DijkstraSP struct {
distTo []float32
edgeTo []*DirectedEdge
pq *IndexMinPQ
}
// NewDijkstraSP ...
func NewDijkstraSP(g *EdgeWeightedDigraph, s int) *DijkstraSP {
edgeTo := make([]*DirectedEdge, g.V())
distTo := make([]float32, g.V())
for v := 0; v < g.V(); v++ {
distTo[v] = PositiveInfinity
}
distTo[s] = 0.0
pq := NewIndexMinPQ(g.V())
d := &DijkstraSP{distTo, edgeTo, pq}
pq.Insert(s, FloatPQItem(distTo[s]))
for !pq.IsEmpty() {
d.relax(g, pq.DelMin())
}
return d
}
func (d *DijkstraSP) relax(g *EdgeWeightedDigraph, v int) {
for _, e := range g.Adj(v) {
w := e.To()
if d.distTo[w] > d.distTo[v]+e.Weight() {
d.distTo[w] = d.distTo[v] + e.Weight()
d.edgeTo[w] = e
if d.pq.Contains(w) {
d.pq.ChangeKey(w, FloatPQItem(d.distTo[w]))
} else {
d.pq.Insert(w, FloatPQItem(d.distTo[w]))
}
}
}
}
// DistTo ...
func (d *DijkstraSP) DistTo(v int) float32 {
return d.distTo[v]
}
// HasPathTo ...
func (d *DijkstraSP) HasPathTo(v int) bool {
return d.distTo[v] < PositiveInfinity
}
// PathTo ...
func (d *DijkstraSP) PathTo(v int) (edges []*DirectedEdge) {
if !d.HasPathTo(v) {
return nil
}
for e := d.edgeTo[v]; e != nil; e = d.edgeTo[e.From()] {
// stack
edges = append([]*DirectedEdge{e}, edges...)
}
return
}