• Explore
• My scripts
• Calculator

Chemins de poids minimal dans un graphe : l’algorithme de Dijkstra.

# fichier : dijkstra2.py
#  auteur : Pascal CHAUVIN
#    date : 2020/04/22

# version : 0.5.2

# Tous les caracteres non ASCII sont volontairement omis ; l'affichage 
# est adapte a l'ecran de la calculatrice NumWorks.

# L'algorithme de DIJKSTRA calcule le chemin de poids minimal 
# d'un sommet vers tous les autres sommets, pour un graphe 
# connexe pondere (oriente ou non) dont les poids des aretes 
# sont des nombres tous positifs.

def affiche(t):
  """ Affichage "elegant" de la table t """
  num_lignes = len(t)
  num_colonnes = max([len(l) for l in t])
  for y in range(num_lignes):
    u = list(t[y]) + [""] * num_colonnes
    u = u[:num_colonnes]
    for x in range(len(u)):
      v = u[x]
      if type(v) is tuple:
        # nombre affiche sur 3 ch. et 1 car. pour le sommet
        print("|{:>3},{}".format(v[0], v[1]), end="")
      else:
        # 5 car. par defaut
        print("|{:^5}".format(str(v)), end="")
    print("|")

def chemin_minimal(graphe, debut, fin, afficher=True):
  """ Algorithme de DIJKSTRA """

  sommets = sorted(graphe.keys())
  lignes = [sommets]
  nouvelle_ligne = []
  for s in sommets:
    if s is debut:
      nouvelle_ligne.append((0, debut))
    else:
      nouvelle_ligne.append((float('inf'), debut))
  lignes.append(nouvelle_ligne)

  # On dresse le tableau dans tous les cas, meme pour debut et fin 
  # egaux.

  fixe = debut
  poids = 0

  chemin = {}

  visites = [s for s in sommets if s is not debut]

  while len(visites) > 0:
    nouvelle_ligne = lignes[-1][:]
    i_fixe = sommets.index(fixe)
    nouvelle_ligne[i_fixe] = "-"
    for i in range(len(nouvelle_ligne)):
      if not(nouvelle_ligne[i] is "-"):
        if lignes[0][i] in graphe[fixe]:
          p = poids + graphe[fixe][lignes[0][i]]
          if p < lignes[-1][i][0]:
            nouvelle_ligne[i] = (p, fixe)
    lignes.append(nouvelle_ligne)

    l = [t for t in nouvelle_ligne if type(t) is tuple]
    t_min = min(l, key=lambda u: u[0])
    i_fixe = nouvelle_ligne.index(t_min)

    poids = nouvelle_ligne[i_fixe][0]
    fixe = lignes[0][i_fixe]

    chemin[fixe] = nouvelle_ligne[i_fixe]

    del visites[visites.index(fixe)]

  if afficher:
    affiche(lignes)

  if debut is fin:
    print(list(debut), 0)
  else:
    route = []
    n = fin
    while n != debut:
      route.append(n)
      n = chemin[n][1]
    route.append(debut)
    route.reverse()
    print(route, chemin[fin][0])

def test_1():
  """ Le graphe g est non oriente. """
  g = {
    "a": {"b": 16, "d": 30},
    "b": {"a": 16, "d": 36, "f": 40},
    "c": {"d": 32, "e": 15, "f": 27},
    "d": {"a": 30, "b": 36, "c": 32, "e": 29, "g": 60},
    "e": {"c": 15, "d": 29, "f": 30, "g": 33},
    "f": {"b": 40, "c": 27, "e": 30, "g": 28},
    "g": {"d": 60, "e": 33, "f": 28}
  }
  print("--- chemin de a vers g ---")
  chemin_minimal(g, "a", "g", afficher=False)

def test_2():
  """ g est un graphe oriente. """
  g = {
    "A": {"B": 1, "C": 4, "D": 3},
    "B": {"A": 2},
    "C": {"B": 1},
    "D": {"A": 1, "C": 2}
  }
  print("--- graphe oriente ---")
  print("--- chemin de A vers C ---")
  chemin_minimal(g, "A", "C")

  print("--- chemin inverse ---")
  chemin_minimal(g, "C", "A")

def test_3():
  """ g est un graphe oriente. """
  g = {
    "a": {"b": 1, "c": 4, "d": 1},
    "b": {"a": 1, "c": 1, "d": 2},
    "c": {"a": 4, "b": 1},
    "d": {"a": 1, "c": 2}
  }
  print("--- graphe oriente ---")
  print("--- chemin de a vers d ---")
  chemin_minimal(g, "a", "d")

  print("--- chemin de b vers b ---")
  chemin_minimal(g, "b", "b")

test_2()