L’algorithme de Dijkstra donne un chemin le plus court dans un graphe et sa longueur (programme de TES spécialité).
def dijkstra(): r,P=range,print #Nouvelle Caledonie novembre 2017 M=[[0 ,8 ,0 ,18,13,0 ,0], [8 ,0 ,23,9 ,0 ,0 ,0], [0 ,23,0 ,10,0 ,4 ,3], [18,9 ,10,0 ,0 ,7 ,0], [13,0 ,0 ,0 ,0 ,13,0], [0 ,0 ,4 ,7 ,13,0 ,9], [0 ,0 ,3 ,0 ,0 ,9 ,0]] d=ord("A")-65 a=ord("G")-65 inf=float("inf") p=[-1 for s in r(len(M))] D=[inf for s in r(len(M))] D[d]=0 f={i for i in r(len(M))} while f: dmin=inf for s in f: if dmin>D[s]: dmin=D[s] smin=s f-={smin} P("choix "+chr(65+smin)+" "+str(D[smin])+ " venant de "+str(chr(65+p[smin])).replace("@","nulle part")) for s in f: if M[smin][s] and D[smin]+M[smin][s]<D[s]: D[s]=D[smin]+M[smin][s] p[s]=smin s=a pc=[s] while s!=d: s=p[s] pc=[s]+pc P(D[a]) P("-".join([chr(i+65) for i in pc]))