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
|
package graph
// ShortestPath computes a shortest path from v to w.
// Only edges with non-negative costs are included.
// The number dist is the length of the path, or -1 if w cannot be reached.
//
// The time complexity is O((|E| + |V|)⋅log|V|), where |E| is the number of edges
// and |V| the number of vertices in the graph.
func ShortestPath(g Iterator, v, w int) (path []int, dist int64) {
parent, distances := ShortestPaths(g, v)
path, dist = []int{}, distances[w]
if dist == -1 {
return
}
for v := w; v != -1; v = parent[v] {
path = append(path, v)
}
for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
path[i], path[j] = path[j], path[i]
}
return
}
// ShortestPaths computes the shortest paths from v to all other vertices.
// Only edges with non-negative costs are included.
// The number parent[w] is the predecessor of w on a shortest path from v to w,
// or -1 if none exists.
// The number dist[w] equals the length of a shortest path from v to w,
// or is -1 if w cannot be reached.
//
// The time complexity is O((|E| + |V|)⋅log|V|), where |E| is the number of edges
// and |V| the number of vertices in the graph.
func ShortestPaths(g Iterator, v int) (parent []int, dist []int64) {
n := g.Order()
dist = make([]int64, n)
parent = make([]int, n)
for i := range dist {
dist[i], parent[i] = -1, -1
}
dist[v] = 0
// Dijkstra's algorithm
Q := emptyPrioQueue(dist)
Q.Push(v)
for Q.Len() > 0 {
v := Q.Pop()
g.Visit(v, func(w int, d int64) (skip bool) {
if d < 0 {
return
}
alt := dist[v] + d
switch {
case dist[w] == -1:
dist[w], parent[w] = alt, v
Q.Push(w)
case alt < dist[w]:
dist[w], parent[w] = alt, v
Q.Fix(w)
}
return
})
}
return
}
|
