Added Dijkstras shortest path

prakhar1989 · prakhar1989 · commit 66c3c0955215 · 2012-12-05T22:55:11.000+05:30
diff --git a/graph.py b/graph.py
@@ -60,6 +60,7 @@ def add_edge(self, edge, wt=1, label=""):
             if (u!=v):
                 self.node_neighbors[v].append(u)
             self.set_edge_properties((u, v), label=label, weight=wt)
+            self.set_edge_properties((v, u), label=label, weight=wt)
         else:
             raise Exception("Edge (%s, %s) already added in the graph" % (u, v))
 
diff --git a/graph_algorithms.py b/graph_algorithms.py
@@ -18,7 +18,7 @@ def BFS(gr, s):
                 q.append(each)
     return nodes_explored
 
-def shortest_path(gr, s):
+def shortest_hops(gr, s):
     """ Finds the shortest number of hops required
     to reach a node from s. Returns a dict with mapping:
     destination node from s -> no. of hops
@@ -138,3 +138,19 @@ def inner_DFS(digr, node, node_explored, finishing_times):
     global finishing_counter
     # adds nodes based on increasing order of finishing times
     finishing_times.append(node) 
+
+def shortest_path(digr, s):
+    """ Finds the shortest path from s to every other vertex findable
+    from s using Dijkstra's algorithm in O(mn) time """
+    nodes_explored = [s]
+    nodes_unexplored = DFS(digr, s) # all accessible nodes from s
+    dist = {s:0}
+    nodes_unexplored.remove(s)
+    while len(nodes_unexplored) > 0:
+        edge_frontier = [(u, v) for (u, v) in digr.edges() if u in nodes_explored 
+                        and v in nodes_unexplored]
+        min_dist = min([(dist[u] + digr.get_edge_weight((u, v)), v) for (u, v) in edge_frontier])
+        nodes_explored.append(min_dist[1])
+        nodes_unexplored.remove(min_dist[1])
+        dist[min_dist[1]] = min_dist[0]
+    return dist
diff --git a/graph_algorithms_test.py b/graph_algorithms_test.py
@@ -39,17 +39,17 @@ def test_dfs_directed_graph(self):
         self.assertEqual(len(DFS(self.digr, "c")), 7)
         self.assertEqual(len(DFS(self.digr, "f")), 1)
 
-    def test_shortest_path_undirected_graph(self):
-        self.assertEqual(shortest_path(self.gr, "s")["c"], 2)
-        self.assertEqual(shortest_path(self.gr, "c")["s"], 2)
-        self.assertEqual(shortest_path(self.gr, "s")["s"], 0)
-        self.assertEqual(shortest_path(self.gr, "c")["j"], float('inf'))
+    def test_shortest_hops_undirected_graph(self):
+        self.assertEqual(shortest_hops(self.gr, "s")["c"], 2)
+        self.assertEqual(shortest_hops(self.gr, "c")["s"], 2)
+        self.assertEqual(shortest_hops(self.gr, "s")["s"], 0)
+        self.assertEqual(shortest_hops(self.gr, "c")["j"], float('inf'))
 
-    def test_shortest_path_directed_graph(self):
-        self.assertEqual(shortest_path(self.digr, "s")["f"], 3)
-        self.assertEqual(shortest_path(self.digr, "f")["s"], float('inf'))
-        self.assertEqual(shortest_path(self.digr, "s")["s"], 0)
-        self.assertEqual(shortest_path(self.digr, "s")["c"], float('inf'))
+    def test_shortest_hops_directed_graph(self):
+        self.assertEqual(shortest_hops(self.digr, "s")["f"], 3)
+        self.assertEqual(shortest_hops(self.digr, "f")["s"], float('inf'))
+        self.assertEqual(shortest_hops(self.digr, "s")["s"], 0)
+        self.assertEqual(shortest_hops(self.digr, "s")["c"], float('inf'))
 
     def test_undirected_connected_component(self):
         self.assertEqual(len(undirected_connected_components(self.gr)), 3)
@@ -79,5 +79,26 @@ def test_directed_connected_components(self):
         digr2.add_edges([("h", "j"), ("j", "k"), ("k", "h")])
         self.assertEqual(len(directed_connected_components(digr2)), 4)
 
+    def test_shortest_path_in_directed_graph(self):
+        digr = digraph()
+        digr.add_nodes(["a", "b", "c", "d", "e", "f"])
+        digr.add_edge(("a", "b"), 7)
+        digr.add_edge(("a", "c"), 9)
+        digr.add_edge(("a", "f"), 14) 
+        digr.add_edge(("f", "e"), 9)
+        digr.add_edge(("c", "f"), 2)
+        digr.add_edge(("c", "d"), 11)
+        digr.add_edge(("b", "c"), 10)
+        digr.add_edge(("b", "d"), 15)
+        digr.add_edge(("d", "e"), 6)
+        self.assertEqual(shortest_path(digr, "a")["a"], 0)
+        self.assertEqual(shortest_path(digr, "a")["b"], 7)
+        self.assertEqual(shortest_path(digr, "a")["c"], 9)
+        self.assertEqual(shortest_path(digr, "a")["d"], 20)
+        self.assertEqual(shortest_path(digr, "a")["e"], 20)
+        self.assertEqual(shortest_path(digr, "a")["f"], 11)
+
+
+    
 if __name__ == "__main__":
     unittest.main()
