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 ).
Les applications suivantes et la correction guidée sont réservées aux membres Premium
La méthode et sa première application corrigée restent en accès libre. Le Premium débloque les applications suivantes, l'aide IA et le suivi de ta maîtrise.