-
Notifications
You must be signed in to change notification settings - Fork 92
/
dijkstra_test.go
100 lines (86 loc) · 3.24 KB
/
dijkstra_test.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
package graph
import "testing"
type dijkstraTestCase struct {
graph []*dijkstraVertex
distances []int
}
/*
TestDijkstra tests solution(s) with the following signature and problem description:
dijkstraVertex struct {
val int
distance int
discovered bool
edges []*weightedEdge
}
weightedEdge struct {
edge *dijkstraVertex
weight int
}
func Dijkstra(graph []*dijkstraVertex, source *dijkstraVertex)
Implement Dijkstra's algorithm. Given a single sourced edge weighted graph, find the
shortest path from the source of the graph to every node and set it to the distance
field of the node.
5
(4) ↖ (1)
2 ─────→ 4
(1) ↑ (2) ↗ (1)
1 ──→ 3
For the above graph, the shortest paths for each node are {0, 1, 3, 5, 8}.
*/
func TestDijkstra(t *testing.T) {
tests := []*dijkstraTestCase{
{
graph: newGraph(2),
distances: []int{0, 10},
},
{
graph: newGraph(5),
distances: []int{0, 1, 3, 5, 8},
},
{
graph: newGraph(4),
distances: []int{0, 5, 3, 10},
},
{
graph: newGraph(3),
distances: []int{0, 3, 5},
},
{
graph: newGraph(6),
distances: []int{0, 1, 3, 4, 6, 10},
},
}
addEdges(tests)
for i, test := range tests {
Dijkstra(test.graph, test.graph[0])
for j, v := range test.graph {
if v.distance != test.distances[j] {
t.Errorf("Test Case %d, Vertex %d distance: got %d, expected %d", i, v.val, v.distance, test.distances[j])
}
}
}
}
func newGraph(edges int) []*dijkstraVertex {
graph := make([]*dijkstraVertex, edges)
for i := range edges {
graph[i] = &dijkstraVertex{val: i}
}
return graph
}
func addEdges(tests []*dijkstraTestCase) {
tests[0].graph[0].edges = []*weightedEdge{{edge: tests[0].graph[1], weight: 10}}
tests[1].graph[0].edges = []*weightedEdge{{edge: tests[1].graph[1], weight: 1}, {edge: tests[1].graph[2], weight: 3}}
tests[1].graph[1].edges = []*weightedEdge{{edge: tests[1].graph[2], weight: 2}, {edge: tests[1].graph[3], weight: 4}}
tests[1].graph[2].edges = []*weightedEdge{{edge: tests[1].graph[3], weight: 3}, {edge: tests[1].graph[4], weight: 5}}
tests[1].graph[3].edges = []*weightedEdge{{edge: tests[1].graph[4], weight: 5}}
tests[2].graph[0].edges = []*weightedEdge{{edge: tests[2].graph[1], weight: 5}, {edge: tests[2].graph[2], weight: 3}}
tests[2].graph[1].edges = []*weightedEdge{{edge: tests[2].graph[2], weight: 2}, {edge: tests[2].graph[3], weight: 6}}
tests[2].graph[2].edges = []*weightedEdge{{edge: tests[2].graph[3], weight: 7}}
tests[3].graph[0].edges = []*weightedEdge{{edge: tests[3].graph[1], weight: 3}, {edge: tests[3].graph[2], weight: 5}}
tests[3].graph[1].edges = []*weightedEdge{{edge: tests[3].graph[2], weight: 2}}
tests[4].graph[0].edges = []*weightedEdge{{edge: tests[4].graph[1], weight: 1}, {edge: tests[4].graph[2], weight: 4}}
tests[4].graph[1].edges = []*weightedEdge{{edge: tests[4].graph[2], weight: 2}, {edge: tests[4].graph[3], weight: 5}}
tests[4].graph[2].edges = []*weightedEdge{{edge: tests[4].graph[3], weight: 1}, {edge: tests[4].graph[4], weight: 3}}
tests[4].graph[3].edges = []*weightedEdge{{edge: tests[4].graph[4], weight: 2}, {edge: tests[4].graph[1], weight: 1}}
tests[4].graph[4].edges = []*weightedEdge{{edge: tests[4].graph[5], weight: 4}}
}