Comment implémenter l'algorithme de Dijkstra pour les plus courts chemins ?
Calculer, dans un graphe pondéré à poids positifs, la distance minimale du sommet source à chacun des autres sommets.
Sur le graphe pondéré à sommets d'arêtes , , , , , , calculer les distances minimales depuis la source .
Calculer, dans un graphe pondéré à poids positifs, la distance minimale du sommet source à chacun des autres sommets.
À chaque étape, on sélectionne parmi les sommets non visités celui dont la distance provisoire est minimale (ce choix est correct car les poids sont positifs), on le marque visité, puis on relâche ses voisins en posant pour chaque voisin non visité.
dist à partout sauf dist[s] = 0, et un ensemble visites vide ; je choisis une représentation du graphe (dictionnaire {u: [(v, poids), ...]} ou matrice d'adjacence pondérée).dist[u], je l'ajoute à visites, puis pour chaque voisin de non visité je relâche : dist[v] = min(dist[v], dist[u] + w(u,v)).dist : dist[t] est la distance minimale de à (ou si n'est pas accessible).Sur le graphe pondéré à sommets d'arêtes , , , , , , calculer les distances minimales depuis la source .
dist à partout sauf dist[s] = 0, et un ensemble visites vide ; je choisis une représentation du graphe (dictionnaire {u: [(v, poids), ...]} ou matrice d'adjacence pondérée).Je code le graphe en dictionnaire de listes de couples et j'initialise.
import math
G = {0:[(1,4),(2,1)], 1:[(0,4),(2,2),(3,1)], 2:[(0,1),(1,2),(3,5)], 3:[(1,1),(2,5),(4,3)], 4:[(3,3)]}
n = 5
dist = [math.inf]*n
dist[0] = 0
visites = set()
dist[u], je l'ajoute à visites, puis pour chaque voisin de non visité je relâche : dist[v] = min(dist[v], dist[u] + w(u,v)).Je boucle : je choisis à chaque tour le sommet non visité de distance minimale, puis je relâche ses voisins.
while len(visites) < n:
u = min((s for s in range(n) if s not in visites), key=lambda s: dist[s])
if dist[u] == math.inf:
break
visites.add(u)
for v, w in G[u]:
if v not in visites and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
dist : dist[t] est la distance minimale de à (ou si n'est pas accessible).À la fin de la boucle, on obtient le tableau des distances.
print(dist) # [0, 3, 1, 4, 7]
Distances depuis : (plus court chemin de longueur ).
Écrire une fonction dijkstra(G, s, n) qui renvoie le tableau des distances depuis dans un graphe codé par dictionnaire {u: [(v, poids)]}.
Appliquer l'algorithme précédent sur un graphe triangle d'arêtes , , depuis la source .
Sur le graphe pondéré à sommets d'arêtes , , , , , calculer les distances minimales depuis la source .
Implémenter une variante qui renvoie aussi le tableau des prédécesseurs pour reconstruire les plus courts chemins depuis la source.
Crée ton compte pour accéder à la fiche et aux exercices