dijkstra.py

Created on June 16, 2018

815 Bytes

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]))