from heapq import heappush, heappop
from itertools import permutations

G = {k: {} for k in ("Laad", "A", "B", "C", "D", "E")}
for a, b, w in [("Laad","A",2), ("Laad","B",4), ("A","B",1),
                ("A","C",5), ("B","C",2), ("B","D",5),
                ("C","D",1), ("C","E",4), ("D","E",2)]:
    G[a][b] = G[b][a] = w

def dijkstra(g, start):
    afstand = {v: float("inf") for v in g}
    vorig = {}
    afstand[start] = 0
    wachtrij = [(0, start)]
    while wachtrij:
        d, v = heappop(wachtrij)
        if d != afstand[v]:  # oude kandidaat na een betere route
            continue
        for buur, w in g[v].items():
            if w < 0:
                raise ValueError("Dijkstra vereist niet-negatieve gewichten")
            nieuw = d + w
            if nieuw < afstand[buur]:
                afstand[buur] = nieuw
                vorig[buur] = v
                heappush(wachtrij, (nieuw, buur))
    return afstand, vorig

def pad(vorig, doel):
    route = [doel]
    while route[-1] in vorig:
        route.append(vorig[route[-1]])
    return route[::-1]

d, v = dijkstra(G, "Laad")
print("afstanden", d)
print("route", " -> ".join(pad(v, "E")))
print("rijtijd", d["E"] / 0.20, "s")
stations = ("A", "C", "E")
alle = {k: dijkstra(G, k)[0] for k in ("Laad",)+stations}
def rondelengte(volgorde):
    p = ("Laad",)+volgorde+("Laad",)
    return sum(alle[a][b] for a,b in zip(p,p[1:]))
best = min(permutations(stations), key=rondelengte)
print("meetronde", best, rondelengte(best), "m")
assert d["E"] == 8 and rondelengte(best) == 16