first draft

1 files changed, 39 insertions, 0 deletions

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')
+
+