/
dijkstra.go
86 lines (80 loc) · 1.99 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
package graph
import (
"container/list"
)
type VertexInfo struct {
ID int
Distance int
Path []int
}
type DLList struct {
*list.List
}
func (l *DLList) InsertOrdered(v *VertexInfo) {
if l.Len() == 0 {
l.PushFront(v)
return
}
back := l.Back()
if back.Value.(*VertexInfo).Distance < v.Distance {
l.InsertAfter(v, back)
return
}
current := l.Front()
for current.Value.(*VertexInfo).Distance < v.Distance && current.Value.(*VertexInfo).ID != v.ID {
next := current.Next()
if next == nil {
break
}
current = next
}
if current.Value.(*VertexInfo).ID == v.ID {
return
}
l.InsertAfter(v, current)
}
func (l *DLList) PopFront() *VertexInfo {
e := l.Front()
l.Remove(e)
return e.Value.(*VertexInfo)
}
func DijkstraShortest(g Graph, from, to int) (int, []int, map[int]*VertexInfo) {
vertices := map[int]*VertexInfo{
from: &VertexInfo{ID: from, Path: []int{from}},
}
visited := map[int]bool{}
toVisit := DLList{List: list.New()}
toVisit.InsertOrdered(vertices[from])
for toVisit.Len() > 0 {
visiting := toVisit.PopFront() // take the first to visit
for _, k := range g[visiting.ID].Order {
if visited[k] { // don't visit fully visited
continue
}
v := g[visiting.ID].Neighbours[k]
lp := len(vertices[visiting.ID].Path)
if _, exist := vertices[k]; !exist { // if doenst exist, add vertex
vertices[k] = &VertexInfo{
ID: k,
Distance: v + vertices[visiting.ID].Distance,
Path: append(vertices[visiting.ID].Path[:lp:lp], k),
}
toVisit.InsertOrdered(vertices[k])
} else {
newDistance := v + vertices[visiting.ID].Distance
if vertices[k].Distance > newDistance { // update only if better
vertices[k].Distance = newDistance
vertices[k].Path = append(vertices[visiting.ID].Path[:lp:lp], k)
}
}
}
if visiting.ID == to {
break
}
visited[visiting.ID] = true // mark visited
}
if _, exist := vertices[to]; !exist {
return 0, nil, nil
}
return vertices[to].Distance, vertices[to].Path, vertices
}