From 30879149f544a6cb1ebbeb3c27c467c479d0d448 Mon Sep 17 00:00:00 2001 From: jullinator Date: Fri, 17 Aug 2018 23:56:49 +0200 Subject: first draft --- test_dijkstra.py | 39 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 39 insertions(+) create mode 100644 test_dijkstra.py (limited to 'test_dijkstra.py') diff --git a/test_dijkstra.py b/test_dijkstra.py new file mode 100644 index 0000000..76799de --- /dev/null +++ b/test_dijkstra.py @@ -0,0 +1,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') + + -- cgit v1.2.1