Calculateur Dijkstra

Pseudocode

Dijkstra est un algorithme glouton dont la correction repose sur une seule affirmation: le sommet non fixé le plus proche ne pourra plus être amélioré. Une file de priorité fournit ce sommet en O(log V).

Dijkstra(graphe, source):
    pour chaque sommet v: dist[v] = infini
    dist[source] = 0
    fp = file de priorité contenant (0, source)

    tant que fp est non vide:
        (d, u) = fp.extraireMin()
        si d > dist[u]: continuer     // entrée périmée
        pour chaque arête (u, v, w):
            si dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                fp.inserer((dist[v], v))

Le test des entrées périmées compte. Plutôt que de diminuer la clé dans le tas, ce que la plupart des bibliothèques standard ne permettent pas, l'usage est d'insérer une entrée en double et d'ignorer toute entrée dont la distance enregistrée ne correspond plus. Cela s'appelle la suppression paresseuse, et c'est pourquoi la file peut contenir jusqu'à E entrées plutôt que V.

Exemple détaillé, étape par étape

Exécute Dijkstra depuis A sur un graphe pondéré où le choix glouton paie, en observant grandir l'ensemble des sommets fixés.

Graphe d'exemple: Arêtes non orientées A-B (4), A-C (2), C-B (1), B-D (5) et C-D (8).

1. Initialiser. dist = A 0, B infini, C infini, D infini. La file contient (0, A).
2. Fixer A à 0. Relâche A-B donnant dist[B] = 4, et A-C donnant dist[C] = 2. La file contient (2, C) et (4, B).
3. Fixer C à 2. C est plus proche que B, il sort donc en premier. Relâche C-B: 2 + 1 = 3, mieux que le 4 enregistré, donc dist[B] = 3 et une nouvelle entrée (3, B) est insérée. Relâche C-D: 2 + 8 = 10, donc dist[D] = 10.
4. Fixer B à 3. L'entrée (3, B) remonte avant l'entrée périmée (4, B). Relâche B-D: 3 + 5 = 8, mieux que 10, donc dist[D] = 8.
5. Écarter l entrée périmée. L'ancienne entrée (4, B) remonte à son tour. Comme 4 dépasse dist[B] qui vaut 3, elle est écartée sans retraiter B. C'est la suppression paresseuse à l'œuvre.
6. Fixer D à 8. Il ne reste rien à améliorer. L'algorithme se termine.

Les distances finales sont A 0, C 2, B 3, D 8, et le plus court chemin vers D passe par A, C, B puis D. Remarque que l'arête directe A-B de poids 4 n'est jamais utilisée: passer par C coûte 3. Remarque aussi que les sommets sont fixés dans l'ordre des distances 0, 2, 3, 8, ce qui est exactement la propriété sur laquelle repose l'argument glouton.

Complexité et son origine

Temps: O((V + E) log V) · Espace: O(V)

Avec un tas binaire, chacun des V sommets est extrait une fois en O(log V), et chacune des E arêtes peut déclencher une insertion en O(log V), d'où O((V + E) log V). Avec la suppression paresseuse, le tas contient jusqu'à E entrées, donc l'extraction coûte O(log E), mais comme E vaut au plus V au carré, log E vaut au plus 2 log V et la borne ne change pas. Un tas de Fibonacci améliore la borne théorique en O(E + V log V) car la diminution de clé devient O(1) amorti, mais les constantes sont assez mauvaises pour que les tas binaires l'emportent en pratique. Sur un graphe dense, un simple parcours de tableau pour trouver le minimum donne O(V au carré), ce qui bat le tas dès que E approche V au carré.

Quand utiliser Algorithme de Dijkstra, et quand l'éviter

Dijkstra est le choix par défaut pour les plus courts chemins pondérés. Ce qui le remplace dépend de celle de ses hypothèses que ton graphe enfreint.

Pièges fréquents

• L utiliser avec des poids négatifs. C'est le mésusage classique. Dijkstra fixe un sommet définitivement quand il quitte la file; une arête négative découverte plus tard l'aurait amélioré, mais il n'est jamais reconsidéré. Le résultat est silencieusement faux plutôt qu'une erreur, ce qui rend le bogue difficile à repérer. Prends Bellman-Ford.
• Omettre le test des entrées périmées. Sans la garde `si d > dist[u]: continuer`, un sommet est retraité une fois par entrée dans la file. L'algorithme termine toujours et donne des réponses correctes, mais il relâche des arêtes inutilement et peut se dégrader fortement sur les graphes à nombreuses améliorations.
• S arrêter à la première vue de la cible. Atteindre la cible pendant un relâchement ne signifie pas que sa distance est définitive. Elle ne l'est qu'une fois la cible extraite de la file. S'arrêter à la découverte donne de mauvaises réponses; s'arrêter à l'extraction est correct et constitue une vraie optimisation.
• Voir un problème dans les arêtes de poids nul. Les poids nuls ne posent aucun problème. Seuls les poids strictement négatifs cassent l'argument, car la preuve gloutonne exige des distances croissantes au sens large le long d'un chemin, et zéro préserve cette propriété.
• Reconstruire tout le graphe à chaque requête. Une exécution de Dijkstra donne les distances de la source vers tous les sommets, pas seulement un. Si tu as besoin de nombreuses sources, c'est un autre problème: envisage Floyd-Warshall ou Johnson plutôt que d'exécuter Dijkstra V fois sans réfléchir.

Questions fréquentes

À quoi sert l'algorithme de Dijkstra?

Il trouve le plus court chemin depuis une source vers tous les autres sommets dans un graphe à poids positifs ou nuls. Il pilote la navigation GPS et les transports en commun, les protocoles de routage comme OSPF et IS-IS, l'analyse de latence réseau, et la recherche de chemin dans les jeux quand aucune heuristique n'est disponible.

Quelle est la complexité temporelle de l'algorithme de Dijkstra?

O((V + E) log V) avec un tas binaire, l'implémentation standard. Un tas de Fibonacci l'abaisse à O(E + V log V) en théorie, mais les constantes rendent généralement les tas binaires plus rapides. Sur les graphes denses, un parcours de tableau donne O(V au carré), ce qui peut battre le tas dès que E approche V au carré.

Pourquoi l'algorithme de Dijkstra échoue-t-il avec des poids négatifs?

Parce qu'il fixe chaque sommet définitivement dès qu'il possède la plus petite distance provisoire de la file, en supposant qu'aucun chemin ultérieur ne pourra être plus court. Une arête négative viole cette hypothèse: un chemin découvert ensuite peut réduire une distance déjà fixée. Comme Dijkstra ne revisite jamais les sommets fixés, il renvoie une réponse fausse sans la moindre erreur.

Quelle est la différence entre Dijkstra et A*?

A* est Dijkstra augmenté d'une estimation heuristique de la distance restante vers une cible donnée. Dijkstra développe les sommets par distance depuis la source et trouve des chemins vers tout; A* développe par coût total estimé et se dirige vers une seule cible, en explorant bien moins de sommets. Avec une heuristique nulle, A* est exactement Dijkstra.

L'algorithme de Dijkstra fonctionne-t-il sur les graphes non orientés?

Oui. Une arête non orientée n'est rien d'autre que deux arêtes orientées de même poids, l'algorithme s'applique donc sans modification. La seule vraie exigence est qu'aucun poids ne soit négatif.