neskoncno = 10000000000

# Graf predstavimo z slovarjem vozlišč, ki slika vozlišče
# v seznam parov (sosed, razdalja)

primer = {
    'a': [('b', 2), ('c', 5)],
    'b': [('c', 1), ('d', 1)],
    'c': [('e', 5)],
    'd': [('e', 2)],
    'e': [('f', 4)],
    'f': [],
}

def vozlisca(g):
    "Vozlišča grafa g."
    return g.keys()

def sosedi(g, x):
    "Sosedi vozlišča x v grafu g, z razdaljami."
    return g[x]

def dijkstra(graf, s):
    """Za dani graf g in izvorno vozlišče s vrni slovarja
       najkrajših razdalj od s do ostalih vozlišče ter
       slovar, ki vsako vozlišče slika v njegovega prednika
       na optimalni poti do s."""

    neobiskani = set(vozlisca(graf))
    razdalja = {}    # razdalja[x] je trenutna najboljša znana razdalja od s do x
    predhodnik = {}  # predhodnik[x] je tisti sosed x, ki optimalno vodi do s

    # Inicializacija
    for x in neobiskani:
        razdalja[x] = neskoncno
        predhodnik[x] = None
    razdalja[s] = 0

    # V = število vozlišč, E = število povezav

    # Dijkstrov postopek izboljšanja razdalj
    while neobiskani:
        # x naj bo tisto neobiskano vozlišče, ki je trenutno najbližje s
        x = None
        # Tu skupaj pridelamo V² korakov
        for y in neobiskani:
            if (x is None) or razdalja[y] < razdalja[x]: x = y

        # zdaj bomo obravnavali x
        neobiskani.remove(x)

        # za vsakega soseda y vozlišča x poskusimo izboljšati
        # najkrajšo pot do y tako, da gremo skozi x (če se splača)
        # Skupno se bo ta zanka izvedla E-krat
        for (y, d_xy) in sosedi(graf, x):
            d = razdalja[x] + d_xy
            if d < razdalja[y]:
                razdalja[y] = d
                predhodnik[y] = x

    return (razdalja, predhodnik)