def contvide(w):
    v={}
    for d in w.keys():
        v[d]="vide"
    return(v)


def popmin(C,d):
    m=float("inf")
    P="vide"
    for R in C:
        if d[R]<m:
            m=d[R]
            P=R
    C.remove(P)
    return(P)


def Dijkstra(w,O):
    d=contvide(w)
    pr=contvide(w)
    m=contvide(w)
    C=set()
    C.add(O)
    pr[O]="-"
    d[O]=0
    while C!=set():
        P=popmin(C,d)
        m[P]="traite"
        for Q in w[P].keys():
            if pr[Q]=="vide":
                C.add(Q)
                pr[Q]=P
                d[Q]=d[P]+w[P][Q]
            elif m[Q]=="vide" and d[P]+w[P][Q]<d[Q]:
                pr[Q]=P
                d[Q]=d[P]+w[P][Q]
    return(d,pr)


def chemin(O,R,pr):
    if R==O:
        return([O])
    else:
        ch=chemin(O,pr[R],pr)
        ch.append(R)
        return(ch)