Algorithmes de chemin le plus court

Les algorithmes de chemin le plus court calculent les itinéraires de poids minimum entre les sommets d'un graphe pondéré, avec différents algorithmes adaptés aux poids non négatifs, aux poids négatifs, et aux requêtes de toutes les paires par rapport aux requêtes à source unique.

Definition

Un chemin le plus court entre deux sommets dans un graphe pondéré est un chemin dont le poids total des arêtes est minimal ; les algorithmes de chemin le plus court calculent de tels chemins et leurs distances, soit d'une source à tous les sommets, soit entre toutes les paires de sommets.

Scope

Ce sujet couvre les chemins les plus courts à source unique (algorithme de Dijkstra pour les poids non négatifs, Bellman-Ford pour les graphes avec des poids négatifs et pour la détection des cycles négatifs), les chemins les plus courts entre toutes les paires (Floyd-Warshall, algorithme de Johnson), et les chemins les plus courts dans les graphes acycliques dirigés. Il aborde le principe de relaxation commun à ces méthodes et le rôle des files de priorité dans une implémentation efficace. Il exclut les chemins les plus courts non pondérés obtenus par recherche en largeur, qui sont traités dans la traversée de graphe.

Core questions

• Comment la relaxation des arêtes affine-t-elle progressivement les estimations de distance vers les véritables distances les plus courtes ?
• Pourquoi l'algorithme de Dijkstra exige-t-il des poids d'arête non négatifs pour être correct ?
• Comment Bellman-Ford gère-t-il les poids négatifs et détecte-t-il les cycles négatifs ?
• Quand le calcul des chemins les plus courts entre toutes les paires est-il plus efficace que la répétition d'une méthode à source unique ?
• Comment les choix de files de priorité affectent-ils le temps d'exécution de l'algorithme de Dijkstra ?

Key concepts

• relaxation des arêtes
• chemins les plus courts à source unique
• algorithme de Dijkstra
• algorithme de Bellman-Ford
• cycles de poids négatif
• chemins les plus courts entre toutes les paires
• algorithme de Floyd-Warshall
• implémentation par file de priorité

Key theories

Relaxation des arêtes et sélection gloutonne

Les algorithmes de chemin le plus court relaxent les arêtes de manière répétée, remplaçant une estimation de distance lorsqu'un itinéraire plus court est trouvé ; l'algorithme de Dijkstra finalise de manière gloutonne le sommet non réglé le plus proche, ce qui est correct précisément parce que les poids des arêtes sont non négatifs.

Programmation dynamique pour les chemins entre toutes les paires

L'algorithme de Floyd-Warshall calcule les chemins les plus courts entre toutes les paires par un programme dynamique sur les sommets intermédiaires, s'exécutant en temps cubique et gérant naturellement les poids d'arête négatifs (sans cycles négatifs).

Clinical relevance

Les algorithmes de chemin le plus court alimentent les services de navigation et de cartographie, les protocoles de routage de paquets dans les réseaux, la planification d'itinéraires en logistique, et tout système qui trouve les chemins de moindre coût à travers un réseau pondéré, y compris la recherche de chemin dans les jeux et les calculs de distance-ressource en analyse spatiale.

History

Dijkstra a publié son algorithme de chemin le plus court à source unique en 1959. L'algorithme de Bellman-Ford, gérant les poids négatifs, est issu des travaux de Bellman, Ford et Moore à la fin des années 1950. L'algorithme de Floyd de 1962, s'appuyant sur la méthode de fermeture transitive de Warshall, a fourni une solution compacte pour toutes les paires qui reste une référence.

Key figures

• Edsger W. Dijkstra
• Richard Bellman
• Lester Ford
• Robert W. Floyd

Seminal works

• dijkstra1959
• floyd1962
• cormen2009

Frequently asked questions

Pourquoi l'algorithme de Dijkstra ne peut-il pas gérer les poids d'arête négatifs ?

L'algorithme de Dijkstra finalise le sommet non réglé le plus proche et ne le revisite jamais, en supposant qu'aucun chemin ultérieur ne peut être plus court. Une arête négative pourrait créer un tel chemin plus court après qu'un sommet soit réglé, rompant cette hypothèse. Bellman-Ford, qui relaxe toutes les arêtes de manière répétée, est utilisé à la place.

Quand devrais-je utiliser un algorithme pour toutes les paires au lieu d'exécuter Dijkstra à partir de chaque sommet ?

Pour les graphes denses ou lorsque de nombreuses ou toutes les distances source-destination sont nécessaires, le calcul simple en temps cubique de Floyd-Warshall pour toutes les paires est souvent préférable. Pour les graphes creux, l'exécution de Dijkstra (ou de l'algorithme de Johnson pour les poids négatifs) à partir de chaque source peut être asymptotiquement plus rapide.