neskoncno = 10000000000

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

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 dijsktra(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

    # Dijkstrov postopek izboljšanja razdalj
    while neobiskani:
        # x naj bo tisto neobiskano vozlišče, ki je trenutno najbližje s
        x = None
        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)
        for (y, d_yx) in sosedi(graf, x):
            d = razdalja[x] + d_yx
            if d < razdalja[y]:
                razdalja[y] = d
                predhodnik[y] = x

    return (razdalja, predhodnik)