Dijkstra

dijkstra.py

from collections import OrderedDict

nodes = {
    "a": {"a": 0, "b": 4, "c": 1},
    "b": {"b": 0, "d": 2},
    "c": {"c": 0, "b": 5, "d": 6},
    "d": {"d": 0, "k": 7},
    "k": {"k": 0}
}

map = OrderedDict(sorted(nodes.items(), key=lambda kv: kv[0]))

edges = {"a": 0}
path = OrderedDict({"a": "start"})

for n, e in map.items():
    m_e = min(e, key=e.get)
    for _n, _e in e.items():
        if edges.get(m_e, 99) + _e < edges.get(_n, 99) and _n not in edges:
            edges[_n] = edges.get(m_e, 99) + _e
            path[_n] = m_e


def trace(path, dest):
    if dest not in path:
        return

    prev = path[dest]

    trace(path, prev)
    print(dest)