Publié · en amélioration
Algorithm
Calculer des plus courts chemins avec Dijkstra, Bellman-Ford et Floyd-Warshall, et construire des arbres couvrants minimaux avec Kruskal et Prim.
Le problème du plus court chemin consiste à trouver, dans un graphe pondéré, le chemin de poids total minimal entre deux sommets. Un arbre couvrant minimal (ACM, ou MST en anglais) est l'ensemble d'arêtes le moins coûteux qui relie tous les sommets d'un graphe non orienté sans former de cycle. Les algorithmes clés de ce thème sont Dijkstra, Bellman-Ford, Floyd-Warshall, le BFS 0-1, Kruskal et Prim.
Ces algorithmes tournent dans les applications de navigation, dans les protocoles de routage comme OSPF et RIP, dans la recherche de chemin des jeux vidéo, dans la conception de réseaux de câbles ou de canalisations et dans le clustering. Ils reviennent souvent en entretien technique, car ils montrent si l'on sait modéliser un problème sous forme de graphe et choisir l'algorithme adapté aux poids : négatifs ou non, uniquement 0 et 1, graphe creux ou dense.
Commencez par maîtriser le BFS et les files de priorité (tas). Apprenez ensuite la relaxation, l'opération commune à tous les algorithmes de plus court chemin, et déroulez Dijkstra à la main sur un petit graphe. Voyez ensuite pourquoi les arêtes négatives imposent Bellman-Ford, implémentez Kruskal avec union-find, puis terminez par des exercices qui appliquent Dijkstra à un graphe d'états étendu.
Tous les algorithmes de plus court chemin reposent sur la relaxation : vérifier si passer par u donne un chemin plus court vers v. Seul l'ordre des relaxations change d'un algorithme à l'autre.
Avec des poids positifs ou nuls, un tas binaire extrait et fixe à chaque étape le sommet le plus proche, ce qui donne toutes les distances depuis une source en O((V + E) log V).
Bellman-Ford accepte les arêtes négatives et détecte les cycles négatifs ; Floyd-Warshall calcule la distance entre toutes les paires de sommets en O(V^3).
Kruskal ajoute les arêtes de la plus légère à la plus lourde et évite les cycles grâce à union-find ; Prim fait grandir un seul arbre par son arête sortante la moins chère. La propriété de coupe garantit que les deux sont corrects.
heapq extrait les paires (distance, sommet) par distance croissante ; une paire dont la distance dépasse la valeur enregistrée est périmée et ignorée. Quand la distance d'un voisin s'améliore, le code la met à jour et insère une nouvelle paire. python dijkstra.py affiche les plus courtes distances depuis A : {'A': 0, 'B': 3, 'C': 1, 'D': 4}.
dijkstra.py
import heapq
def dijkstra(graph, source):
dist = {source: 0}
heap = [(0, source)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue # stale entry
for v, w in graph[u]:
nd = d + w
if nd < dist.get(v, float("inf")):
dist[v] = nd
heapq.heappush(heap, (nd, v))
return dist
graph = {
"A": [("B", 4), ("C", 1)],
"B": [("D", 1)],
"C": [("B", 2), ("D", 5)],
"D": [],
}
print(dijkstra(graph, "A")) # {'A': 0, 'B': 3, 'C': 1, 'D': 4}
python dijkstra.pySix chapitres pour aller de l'installation aux notions essentielles de Plus courts chemins et arbres couvrants.
Posez vos questions, partagez votre expérience et échangez vos avis sur Plus courts chemins et arbres couvrants.
Aucune discussion pour l'instant. Lancez la première.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.
Soyez le premier à commenter.