about summary refs log tree commit diff
path: root/deepmind/dijkstra.py
blob: 6975dbe4d1d61d4f79a17c40d16c908be1909410 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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.")