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
|
import Graph
def dijkstra(adjacency_list, source, target):
""" To be implemented by students. Should return (distance, path).
Path should be a list of the vertices in the shortest path
including the source and target. """
return 6.433, ['A', 'C', 'D']
def test_dijkstra():
vertices = [
('A', 0, 0),
('B', 2, 2),
('C', 2, -2),
('D', 4, 1),
('E', 4, -2),
('F', 6, 1)
]
edges = [
('A', 'B'),
('A', 'C'),
('C', 'D'),
('B', 'C'),
('D', 'F'),
('B', 'E'),
('A', 'F')
]
graph = Graph.Dijkstra(vertices, edges, 'A', 'D')
dist1, path1 = graph.get_shortest_path()
dist2, path2 = dijkstra(graph.adjacency_list, graph.source, graph.target)
assert abs(dist1-dist2) < 1e-3
print('Correct distance')
assert path1 == path2
print('Correct path')
|
