about summary refs log tree commit diff
path: root/scratch/data_structures_and_algorithms/dijkstra-shortest-path.py
blob: 03907f604044ce75479aaafcf7e4a6b472198c3e (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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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))