Algorithme de Dijkstra
Dernière mise à jour
L'algorithme de Dijkstra trouve le plus court chemin depuis un nœud source vers tous les autres nœuds d'un graphe dont les poids d'arête sont non négatifs. Il conserve une distance provisoire pour chaque nœud, fixe de façon répétée le nœud non fixé ayant la plus petite distance provisoire et relâche ses arêtes, en mettant à jour la distance d'un voisin chaque fois qu'un itinéraire plus court passant par le nœud courant est trouvé. Appuyez sur lecture ci-dessus pour voir les distances diminuer à mesure que chaque nœud est fixé.
L'idée clé est gloutonne : une fois le nœud non fixé le plus proche choisi, sa distance est définitive, car tout autre itinéraire vers lui devrait passer par un nœud déjà plus éloigné. Avec une file de priorité à tas binaire, Dijkstra s'exécute en temps O((V + E) log V). Il exige des poids non négatifs : utilisez Bellman-Ford si les arêtes peuvent être négatives.
Complexité en temps et en espace
| Implémentation | Complexité | Remarques |
|---|---|---|
| Tas binaire | O((V + E) log V) | Le choix courant et pratique |
| Balayage de tableau | O(V²) | Plus simple ; convient aux graphes denses |
| Espace | O(V) | Distances + file de priorité |
| Exige | Poids non négatifs | Les arêtes négatives brisent le choix glouton |
Étape par étape
| Étape | Ce qui se passe |
|---|---|
| 1 | Fixez la distance de la source à 0 et toutes les autres à l'infini. |
| 2 | Choisissez le nœud non fixé ayant la plus petite distance provisoire. |
| 3 | Marquez-le comme fixé : sa plus courte distance est désormais définitive. |
| 4 | Pour chaque voisin, calculez distance-par-le-courant + poids de l'arête. |
| 5 | Si c'est plus petit que la distance actuelle du voisin, relâchez-la. |
| 6 | Répétez jusqu'à ce que tous les nœuds atteignables soient fixés. |
Exemple résolu
Plus courts chemins depuis la source A sur le graphe avec les arêtes A-B=4, A-C=1, C-B=2, C-D=5, B-D=1 :
| Étape | Fixer | Distances | Action |
|---|---|---|---|
| 0 | - | A=0, B=∞, C=∞, D=∞ | Initialiser : source A=0, toutes les autres à l'infini. |
| 1 | A (0) | B=4, C=1, D=∞ | Relâche les arêtes depuis A : fixe B=4, C=1. |
| 2 | C (1) | B=3, D=6 | Par C : B=1+2=3 améliore 4 ; D=1+5=6. |
| 3 | B (3) | D=4 | Par B : D=3+1=4 améliore 6. |
| 4 | D (4) | A=0, C=1, B=3, D=4 | Fixe D ; plus rien à relâcher. Terminé. |
Quand utiliser l'algorithme de Dijkstra
| À utiliser quand | À éviter quand |
|---|---|
| Tous les poids d'arête sont non négatifs | Une arête peut être négative : utilisez Bellman-Ford |
| Vous voulez les plus courts chemins d'une source vers tous les nœuds | Vous voulez les plus courts chemins entre toutes les paires : Floyd-Warshall est plus simple |
| Le graphe est pondéré et vous voulez des distances exactes | Le graphe n'est pas pondéré : un simple BFS est plus rapide et plus simple |
| Vous disposez d'un bon tas ou d'une bonne file de priorité | Vous voulez atteindre vite une seule cible avec une heuristique : utilisez A* |
Code de Dijkstra's Algorithm
Une implémentation propre et exécutable de Dijkstra's Algorithm en Python, JavaScript, Java, C++, C. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de Dijkstra's Algorithm en Python
Python
1import heapq2
3
4def dijkstra(graph, start):5 dist = {node: float("inf") for node in graph}6 dist[start] = 07 pq = [(0, start)]8 while pq:9 d, node = heapq.heappop(pq)10 if d > dist[node]:11 continue # stale entry, a shorter path was already found12 for neighbor, weight in graph[node]:13 new_dist = d + weight14 if new_dist < dist[neighbor]:15 dist[neighbor] = new_dist16 heapq.heappush(pq, (new_dist, neighbor))17 return dist18
19
20graph = {21 "A": [("B", 4), ("C", 1)],22 "B": [("D", 1)],23 "C": [("B", 2), ("D", 5)],24 "D": [("E", 3)],25 "E": [],26}27
28for node, d in dijkstra(graph, "A").items():29 print(f"A -> {node}: {d}")Code de Dijkstra's Algorithm en JavaScript
JavaScript
1const graph = {2 A: { B: 4, C: 2 },3 B: { C: 5, D: 10 },4 C: { E: 3 },5 D: { F: 11 },6 E: { D: 4 },7 F: {},8};9
10function dijkstra(source) {11 const dist = {};12 const visited = new Set();13 for (const node in graph) dist[node] = Infinity;14 dist[source] = 0;15 while (visited.size < Object.keys(graph).length) {16 // JS has no built-in heap: linear scan for the closest node (O(V^2))17 let u = null;18 for (const node in dist) {19 if (!visited.has(node) && (u === null || dist[node] < dist[u])) {20 u = node;21 }22 }23 if (dist[u] === Infinity) break;24 visited.add(u);25 for (const [v, w] of Object.entries(graph[u])) {26 if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;27 }28 }29 return dist;30}31
32console.log("Shortest distances from A:", dijkstra("A"));Code de Dijkstra's Algorithm en Java
Java
1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4import java.util.PriorityQueue;5
6public class Main {7 public static void main(String[] args) {8 int n = 6;9 List<List<int[]>> adj = new ArrayList<>();10 for (int i = 0; i < n; i++) adj.add(new ArrayList<>());11 int[][] edges = {12 {0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 5},13 {2, 3, 8}, {3, 4, 3}, {2, 5, 10}, {4, 5, 2}14 };15 for (int[] e : edges) {16 adj.get(e[0]).add(new int[]{e[1], e[2]});17 adj.get(e[1]).add(new int[]{e[0], e[2]});18 }19
20 int[] dist = new int[n];21 Arrays.fill(dist, Integer.MAX_VALUE);22 dist[0] = 0;23 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);24 pq.add(new int[]{0, 0}); // {node, distance}25 while (!pq.isEmpty()) {26 int[] cur = pq.poll();27 int node = cur[0], d = cur[1];28 if (d > dist[node]) continue; // stale queue entry29 for (int[] edge : adj.get(node)) {30 int next = edge[0], nd = d + edge[1];31 if (nd < dist[next]) {32 dist[next] = nd;33 pq.add(new int[]{next, nd});34 }35 }36 }37 System.out.println("Shortest distances from 0: " + Arrays.toString(dist));38 }39}Code de Dijkstra's Algorithm en C++
C++
1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6 const int INF = 1000000000;7 // Weighted directed graph: adj[u] = {(neighbor, weight), ...}8 std::vector<std::vector<std::pair<int, int>>> adj = {9 {{1, 4}, {2, 1}}, // 010 {{3, 1}}, // 111 {{1, 2}, {3, 5}}, // 212 {{4, 3}}, // 313 {}, // 414 };15 int n = static_cast<int>(adj.size());16 std::vector<int> dist(n, INF);17 dist[0] = 0;18 using State = std::pair<int, int>; // (distance, node)19 std::priority_queue<State, std::vector<State>, std::greater<State>> pq;20 pq.push({0, 0});21 while (!pq.empty()) {22 auto [d, u] = pq.top();23 pq.pop();24 if (d > dist[u]) continue; // stale queue entry25 for (auto [v, w] : adj[u]) {26 if (d + w < dist[v]) {27 dist[v] = d + w;28 pq.push({dist[v], v});29 }30 }31 }32 for (int v = 0; v < n; ++v) {33 std::cout << "Distance 0 -> " << v << ": " << dist[v] << "\n";34 }35 return 0;36}Code de Dijkstra's Algorithm en C
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7int main(void) {8 // Weighted directed graph: w[u][v] = 0 means no edge9 int w[N][N] = {10 {0, 4, 1, 0, 0},11 {0, 0, 0, 1, 0},12 {0, 2, 0, 5, 0},13 {0, 0, 0, 0, 3},14 {0, 0, 0, 0, 0},15 };16 int dist[N];17 bool done[N] = {false};18 for (int v = 0; v < N; v++) dist[v] = INF;19 dist[0] = 0;20 // O(V^2) scan for the closest unfinished node (no heap needed here)21 for (int iter = 0; iter < N; iter++) {22 int u = -1;23 for (int v = 0; v < N; v++) {24 if (!done[v] && (u == -1 || dist[v] < dist[u])) u = v;25 }26 if (dist[u] == INF) break; // remaining nodes are unreachable27 done[u] = true;28 for (int v = 0; v < N; v++) {29 if (w[u][v] > 0 && dist[u] + w[u][v] < dist[v]) {30 dist[v] = dist[u] + w[u][v];31 }32 }33 }34 for (int v = 0; v < N; v++) {35 printf("Distance 0 -> %d: %d\n", v, dist[v]);36 }37 return 0;38}FAQ sur l'algorithme de Dijkstra
Quelle est la complexité en temps de l'algorithme de Dijkstra ?
Avec une file de priorité à tas binaire, il s'exécute en
O((V + E) log V). Une version simple qui balaie un tableau pour trouver le minimum à chaque étape est en O(V²), ce qui peut en fait être plus rapide sur les graphes denses. Les deux utilisent un espace O(V).Pourquoi Dijkstra ne fonctionne-t-il pas avec des poids d'arête négatifs ?
Dijkstra suppose qu'une fois le nœud non fixé le plus proche fixé, cette distance est définitive. Une arête négative pourrait créer plus tard un chemin plus court vers un nœud déjà fixé, brisant cette hypothèse. Pour les graphes à poids négatifs, utilisez l'algorithme de Bellman-Ford.
Quelle est la différence entre Dijkstra et le BFS ?
Le BFS trouve les plus courts chemins en comptant les arêtes (chaque poids d'arête vaut effectivement 1), à l'aide d'une simple file. Dijkstra généralise cela aux graphes pondérés en développant toujours le nœud ayant la plus petite distance totale, à l'aide d'une file de priorité. Sur un graphe non pondéré, les deux produisent les mêmes chemins.
Quelle est la différence entre Dijkstra et la recherche A* ?
A* est Dijkstra augmenté d'une heuristique qui estime la distance restante jusqu'à une cible, ce qui oriente la recherche vers ce but au lieu de se développer uniformément dans toutes les directions. Quand l'heuristique est nulle, A* se réduit exactement à Dijkstra. Utilisez A* lorsque vous avez une seule destination et une bonne heuristique admissible ; utilisez Dijkstra lorsque vous avez besoin des distances vers tous les nœuds.
Quand dois-je utiliser Dijkstra plutôt que Bellman-Ford ?
Utilisez Dijkstra dès que tous les poids d'arête sont non négatifs : il est plus rapide,
O((V + E) log V) contre O(V·E) pour Bellman-Ford. Ne choisissez Bellman-Ford que lorsque les arêtes peuvent être négatives ou que vous devez détecter des cycles négatifs. Sur les graphes non négatifs, Dijkstra est presque toujours le meilleur choix.Dijkstra peut-il revisiter un nœud après l'avoir fixé ?
Non : une fois un nœud fixé, sa distance est définitive et il n'est plus jamais relâché. Un piège courant dans les implémentations à tas est de laisser des entrées obsolètes dans la file de priorité après l'amélioration de la distance d'un nœud ; vous devez ignorer un nœud extrait s'il est déjà fixé (sa distance extraite dépasse la distance enregistrée). Oublier cette vérification donne encore des réponses correctes, mais gaspille du travail.
Ressources associées
Plus de visualisations
