about summary refs log tree commit diff
path: root/data_structures_and_algorithms/dijkstra-shortest-path.py
diff options
context:
space:
mode:
authorWilliam Carroll <wpcarro@gmail.com>2020-01-15T14·25+0000
committerWilliam Carroll <wpcarro@gmail.com>2020-01-15T14·25+0000
commitd4d8397e5ffe6734ed5861e48ce475848956a3fe (patch)
tree7f0f8563750a2084ad9a4b9908cbb5316fe6bf10 /data_structures_and_algorithms/dijkstra-shortest-path.py
parentb4ee283b23b8a85c75339e07b0adf43d1c3ca770 (diff)
Add InterviewCake.com examples
Adds some of the code I generated while studying for a role transfer at Google
using the fantastic resource, InterviewCake.com. This work predates the
mono-repo.

I should think of ways to DRY up this code and the code in
crack_the_coding_interview, but I'm afraid I'm creating unnecessary work for
myself that way.
Diffstat (limited to 'data_structures_and_algorithms/dijkstra-shortest-path.py')
-rw-r--r--data_structures_and_algorithms/dijkstra-shortest-path.py48
1 files changed, 48 insertions, 0 deletions
diff --git a/data_structures_and_algorithms/dijkstra-shortest-path.py b/data_structures_and_algorithms/dijkstra-shortest-path.py
new file mode 100644
index 000000000000..03907f604044
--- /dev/null
+++ b/data_structures_and_algorithms/dijkstra-shortest-path.py
@@ -0,0 +1,48 @@
+from collections import deque
+from heapq import heappush, heappop
+from fixtures import weighted_graph
+
+
+def put(t, x, xs):
+    if t == 'stack':
+        return xs.append(x)
+    if t == 'queue':
+        return xs.append(x)
+    if t == 'priority':
+        return heappush(xs, x)
+
+
+def pop(t, xs):
+    if t == 'stack':
+        return xs.pop()
+    if t == 'queue':
+        return xs.popleft()
+    if t == 'priority':
+        return heappop(xs)
+
+
+# shortest_path :: Vertex -> Vertex -> Graph -> [Vertex]
+def shortest_path(a, b, g):
+    """Returns the shortest path from vertex a to vertex b in graph g."""
+    t = 'priority'
+    xs = []
+    seen = set()
+    # Map(Weight, [Vertex])
+    m = {}
+
+    put(t, (0, [a], a), xs)
+
+    while xs:
+        w0, path, v = pop(t, xs)
+
+        seen.add(v)
+        if v == b:
+            m[w0] = path
+        for w1, x in g.get(v):
+            if x not in seen:
+                put(t, (w0 + w1, path + [x], x), xs)
+
+    return m
+
+
+print(shortest_path('a', 'f', graph_a))