dijkstra2.py

Created on June 19, 2018

780 Bytes

Still Dijsktra but with an adjacency list (and you are asked for the start and end).

def dijkstra():

 P=print
# Liban 2017
 M={"A":{"B":5,"C":25,"I":15,"H":10},
 "B":{"A":5,"C":30},
 "C":{"A":25,"B":30,"D":20},
 "D":{"C":20,"E":20,"I":15},
 "E":{"D":20,"F":20,"I":15},
 "F":{"E":20,"G":5,"H":10},
 "G":{"F":5,"H":20},
 "H":{"A":10,"F":10,"G":20,"I":20},
 "I":{"A":15,"D":15,"E":15,"H":20}}

 d=input("Depart ")
 a=input("Arrivee ")

 inf=float("inf")
 p={s:"None" for s in M}
 D={s:inf for s in M}
 D[d]=0
 f=set(M)

 while f:
  smin=min(f,key=lambda s:D[s])
  f-={smin}
  P("choix "+smin+" "+str(D[smin])+
          " venant de "+p[smin].replace("None","nulle part"))
  for s in f:
   if s in M[smin] 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(pc))