diff options
Diffstat (limited to 'test_dijkstra.py')
| -rw-r--r-- | test_dijkstra.py | 46 |
1 files changed, 13 insertions, 33 deletions
diff --git a/test_dijkstra.py b/test_dijkstra.py index 76799de..4f54b4e 100644 --- a/test_dijkstra.py +++ b/test_dijkstra.py @@ -1,39 +1,19 @@ import Graph - +from collections import defaultdict +from heapq import heappush, heappop +import math 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') - ] + """ To be implemented by students. `adjacency_list` is a dictionary with values: (vertice, weight). + Function should return (distance, path). Path should be a list of the vertices in the shortest path + **including** the source and target. If no shortest path is found, it should return (infinity, []) """ - 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') + return math.inf, [source] +if __name__ == '__main__': + try: + Graph.test_dijkstra(dijkstra) + print('Passed ALL tests!') + except AssertionError: + print('Failed one or more tests')
\ No newline at end of file |