subtree(users/wpcarro): docking briefcase at '24f5a642' r/3226

git-subtree-dir: users/wpcarro
git-subtree-mainline: 464bbcb15c09813172c79820bcf526bb10cf4208
git-subtree-split: 24f5a642af3aa1627bbff977f0a101907a02c69f
Change-Id: I6105b3762b79126b3488359c95978cadb3efa789

1 files changed, 26 insertions, 0 deletions

diff --git a/users/wpcarro/scratch/deepmind/part_one/dijkstra.py b/users/wpcarro/scratch/deepmind/part_one/dijkstra.py
new file mode 100644
index 000000000000..6975dbe4d1d6
--- /dev/null
+++ b/users/wpcarro/scratch/deepmind/part_one/dijkstra.py
@@ -0,0 +1,26 @@
+# Doing a practice implementation of Dijkstra's algorithm: a priority-first
+# search.
+from heapq import heappush, heappop
+
+
+class Node(object):
+    def __init__(self, value, children):
+        self.value = value
+        self.children = children
+
+
+def shortest_path(a, b):
+    """Return the shortest path from `a` to `b`."""
+    q = []
+    seen = set()
+    heappush((a.value, a, [a]), q)
+
+    while q:
+        d, node, path = heappop(q)
+        if node == b:
+            return path
+        seen.add(node)
+        for child in node.children:
+            if child not in seen:
+                heappush((d + child.value, child, path + [child]), q)
+    raise Exception("Path between nodes A and B does not exist.")