Merge pull request #16 from rlishtaba/feature/dijkstras

rlishtaba · web-flow · commit ce7cf332483e · 2017-12-10T18:09:11.000-05:00
adding dijkstra SP algorithm
diff --git a/README.md b/README.md
@@ -57,6 +57,7 @@ $ pip install py-algorithms
       - Breadth-First-Search (BFS)
       - Topologial sort
       - Floyd–Warshall algorithm
+      - Dijkstra's algorithm
 
 ---
 
@@ -530,6 +531,55 @@ topological_sort_f1(dag) #=> [#<Vertex(C)>, #<Vertex(B)>, #<Vertex(D)>, #<Vertex
 
 ```
 
+### Dijkstra's algorithm
+
+![](https://upload.wikimedia.org/wikipedia/commons/5/57/Dijkstra_Animation.gif)
+
+```python
+from py_algorithms.graph import new_undirected_graph
+from py_algorithms.graph new_dijkstra_shortest_path
+from py_algorithms.graph reconstruct_dijkstra_path_tree
+
+graph = new_undirected_graph()
+a = graph.insert_vertex('A')
+b = graph.insert_vertex('B')
+c = graph.insert_vertex('C')
+d = graph.insert_vertex('D')
+e = graph.insert_vertex('E')
+
+graph.insert_edge(a, e, 10)
+graph.insert_edge(b, d, 2)
+graph.insert_edge(c, d, 3)
+graph.insert_edge(d, e, 12)
+
+# Start from vertex "c" and grow the cluster.
+paths = new_dijkstra_shortest_path(graph, c)
+
+assert paths[c] == 0
+assert paths[d] == 3
+assert paths[b] == 5
+assert paths[e] == 15
+assert paths[a] == 25
+
+# Reconstructing all the paths dicovered by algorithm
+path_tree = reconstruct_dijkstra_path_tree(graph, c, paths)
+
+
+# Expanding path from vertex "a" to vertex "c" from "path_tree"
+p = a
+stack = [a]
+while p != c:
+    p = path_tree[p].opposite(p)
+    stack.append(p)
+
+assert stack == [a, e, d, c]
+
+
+# The shortest path to reach vertex "a":
+assert stack == [a, e, d, c]
+
+```
+
 ---
 
 ### String Algorithms
diff --git a/py_algorithms/graph/__init__.py b/py_algorithms/graph/__init__.py
@@ -1,16 +1,21 @@
 __all__ = [
     'Graph',
     'Vertex',
-    'directed_graph'
-    'new_undirected_graph'
-    'new_topological_sort_f1'
+    'directed_graph',
+    'new_undirected_graph',
+    'new_topological_sort_f1',
+    'new_dijkstra_shortest_path',
+    'reconstruct_dijkstra_path_tree',
 ]
 
-from typing import List, Callable
+from typing import List, Callable, Dict
 
 from .adt.graph import Graph
 from .adt.vertex import Vertex
+from .adt.edge import Edge
 from .topological_sort import TopologicalSort
+from .dijkstra_shortest_path import DijkstraShortestPath
+from .reconstruct_dijkstra_path_tree import ReconstructDijkstraPathTree
 
 
 def new_directed_graph() -> Graph:
@@ -25,4 +30,13 @@ def new_topological_sort() -> Callable[[Graph], List[Vertex]]:
     return TopologicalSort()
 
 
+def new_dijkstra_shortest_path(graph, source):
+    return DijkstraShortestPath.apply(graph, source)
+
+
+def reconstruct_dijkstra_path_tree(
+        graph: Graph, source: Vertex, dst: Dict[Vertex, int]) -> Dict[Vertex, Edge]:
+    return ReconstructDijkstraPathTree.apply(graph, source, dst)
+
+
 topological_sort_f1 = new_topological_sort()
diff --git a/py_algorithms/graph/dijkstra_shortest_path.py b/py_algorithms/graph/dijkstra_shortest_path.py
@@ -0,0 +1,48 @@
+from typing import Dict
+
+from ..data_structures import new_priority_queue
+from .adt.graph import Graph
+from .adt.vertex import Vertex
+from py_algorithms.data_structures import PriorityQueue
+
+
+class DijkstraShortestPath:
+    @classmethod
+    def apply(cls, graph: Graph, source: Vertex) -> Dict[Vertex, int]:
+        distances = {}
+        visited = {}
+        pq = new_priority_queue(lambda x, y: (x > y) - (x < y) == -1)
+
+        for v in graph.vertices():
+            if v is source:
+                distances[v] = 0
+            else:
+                distances[v] = float('inf')
+            pq.push(v, distances[v])
+
+        while pq.size > 0:
+            u = pq.pop()
+            visited[u] = distances[u]
+
+            for e in graph.incident_edges(u):
+                v = e.opposite(u)
+
+                if v not in visited:
+                    # perform edge relaxation
+                    w = e.element()
+                    if distances[v] > distances[u] + w:
+                        distances[v] = distances[u] + w
+                        pq = cls._rebuild_pq(pq, distances)
+
+        return visited
+
+    @staticmethod
+    def _rebuild_pq(pq: PriorityQueue, dst: Dict[Vertex, int]) -> PriorityQueue:
+        tmp = []
+        while pq.size > 0:
+            tmp.append(pq.pop())
+
+        for v in tmp:
+            pq.push(v, dst[v])
+
+        return pq
diff --git a/py_algorithms/graph/reconstruct_dijkstra_path_tree.py b/py_algorithms/graph/reconstruct_dijkstra_path_tree.py
@@ -0,0 +1,20 @@
+from typing import Dict
+
+from .adt.edge import Edge
+from .adt.graph import Graph
+from .adt.vertex import Vertex
+
+
+class ReconstructDijkstraPathTree:
+    @classmethod
+    def apply(cls, graph: Graph, source: Vertex, dst: Dict[Vertex, int]) -> Dict[Vertex, Edge]:
+        tree = {}
+
+        for v in dst:
+            if v is not source:
+                for e in graph.incident_edges(v, False):
+                    u = e.opposite(v)
+                    w = e.element()
+                    if dst[v] == dst[u] + w:
+                        tree[v] = e
+        return tree
diff --git a/setup.py b/setup.py
@@ -40,7 +40,9 @@
               'DAG', 'directed-acyclic-graph', 'simple-graph',
               'undirected-graph', 'depth-first-search', 'DFS',
               'breadth-first-search', 'BFS', 'Levenshtein Distance',
-              'levenshtein-distance', 'floyd–warshall', 'Floyd', 'Warshall'],
+              'levenshtein-distance', 'dijkstras algorithm', 'dijkstras',
+              'dijkstras shortest path', 'floyd–warshall', 'Floyd', 'Warshall'],
+
     description="Library of Algorithms, Data Structures, "
                 "variety of solutions to common "
                 "CS problems.",
diff --git a/tests/py_algorithms/graph/dijkstra_shortest_path_test.py b/tests/py_algorithms/graph/dijkstra_shortest_path_test.py
@@ -0,0 +1,39 @@
+from py_algorithms.graph import new_dijkstra_shortest_path
+from py_algorithms.graph import new_undirected_graph
+from py_algorithms.graph import reconstruct_dijkstra_path_tree
+
+
+class TestDijkstraShortestPath:
+    def test_apply(self):
+        graph = new_undirected_graph()
+        a = graph.insert_vertex('A')
+        b = graph.insert_vertex('B')
+        c = graph.insert_vertex('C')
+        d = graph.insert_vertex('D')
+        e = graph.insert_vertex('E')
+
+        graph.insert_edge(a, e, 10)
+        graph.insert_edge(b, d, 2)
+        graph.insert_edge(c, d, 3)
+        graph.insert_edge(d, e, 12)
+
+        paths = new_dijkstra_shortest_path(graph, c)
+
+        assert paths[c] == 0
+        assert paths[d] == 3
+        assert paths[b] == 5
+        assert paths[e] == 15
+        assert paths[a] == 25
+
+        path_tree = reconstruct_dijkstra_path_tree(graph, c, paths)
+
+        p = a
+        stack = []
+
+        while p != c:
+            stack.append(p)
+            p = path_tree[p].opposite(p)
+
+        stack.append(p)
+
+        print(stack)
diff --git a/tests/py_algorithms/graph/reconstruct_dijkstra_path_tree_test.py b/tests/py_algorithms/graph/reconstruct_dijkstra_path_tree_test.py
@@ -0,0 +1,36 @@
+from py_algorithms.graph import new_dijkstra_shortest_path
+from py_algorithms.graph import new_undirected_graph
+from py_algorithms.graph import reconstruct_dijkstra_path_tree
+
+
+class TestReconstructDijkstraPathTree:
+    def test_apply(self):
+        graph = new_undirected_graph()
+        a = graph.insert_vertex('A')
+        b = graph.insert_vertex('B')
+        c = graph.insert_vertex('C')
+        d = graph.insert_vertex('D')
+        e = graph.insert_vertex('E')
+
+        graph.insert_edge(a, e, 10)
+        graph.insert_edge(b, d, 2)
+        graph.insert_edge(c, d, 3)
+        graph.insert_edge(d, e, 12)
+
+        paths = new_dijkstra_shortest_path(graph, c)
+
+        assert paths[c] == 0
+        assert paths[d] == 3
+        assert paths[b] == 5
+        assert paths[e] == 15
+        assert paths[a] == 25
+
+        path_tree = reconstruct_dijkstra_path_tree(graph, c, paths)
+
+        p = a
+        stack = [a]
+        while p != c:
+            p = path_tree[p].opposite(p)
+            stack.append(p)
+
+        assert stack == [a, e, d, c]
