Principe fondamental
L'algorithme de Dijkstra calcule les plus courts chemins depuis un sommet source dans un graphe dont toutes les arêtes ont un poids non négatif. Sa complexité temporelle est de O(n²) dans sa version naïve et de O((n + m) log n) avec une optimisation par tas.
L'idée centrale consiste à sélectionner itérativement le sommet non visité ayant la plus petite distance estimée par rapport à la source, puis à utiliser ce sommet pour tenter de raccourcir les distances de ses voisins. Ce processus, appelé relaxation, améliore progressivement les estimations de distance. Une fois un sommet sélectionné, sa distance est définitive car, avec des poids non négatifs, aucun chemin ultérieur ne peut la réduire.
Déroulement de l'algorithme
- Initialiser un tableau de distances avec l'infini, sauf pour la source à zéro.
- Répéter n - 1 fois :
a. Trouver le sommet non visité u avec la plus petite distance estimée.
b. Marquer u comme visité.
c. Pour chaque voisin v de u, si distance[v] > distance[u] + poids(u, v), mettre à jour distance[v].
Preuve de correction par l'absurde
Supposons qu'après avoir marqué un sommet u comme visité (avec distance d_u), il existe un chemin plus court vers u passant par un sommet non visité k. Comme les poids sont non négatifs, la séquence des distances sélectionnées est non décroissante. Ainsi, d_k ≥ d_u. Tout chemin passant par k vers u aurait une longueur d_k + poids(k, u) ≥ d_u (puisque poids(k, u) ≥ 0), ce qui contredit l'existence d'un chemin plus court. Par conséquent, l'algorithme est correct pour les graphes à poids non négatifs.
Implémentations
Version naïve avec liste d'adjacence
Cette version a une complexité de O(n²). On parcourt tous les sommets pour trouver le minimum non visité.
int dijkstra_naive(int source, int destination, int n) {
vector<bool> visite(n + 1, false);
vector<int> dist(n + 1, INF);
dist[source] = 0;
for (int iter = 0; iter < n; ++iter) {
int sommet_min = -1;
for (int i = 1; i <= n; ++i) {
if (!visite[i] && (sommet_min == -1 || dist[i] < dist[sommet_min])) {
sommet_min = i;
}
}
if (sommet_min == -1 || dist[sommet_min] == INF) break;
visite[sommet_min] = true;
for (auto& voisin : liste_adjacence[sommet_min]) {
int v = voisin.first;
int poids = voisin.second;
if (!visite[v] && dist[v] > dist[sommet_min] + poids) {
dist[v] = dist[sommet_min] + poids;
}
}
}
return dist[destination];
}</int></bool>
Version optimisée avec un tas min (file de priorité)
On utilise un tas pour extraire le sommet non visité avec la plus petite distance en O(log n). La complexité devient O((n + m) log n). On gère les doublons en ignorant les sommets déjà visités lors de l'extraction.
#include <queue>
#include <vector>
using Pair = pair<int, int>; // (distance, sommet)
int dijkstra_optimise(int source, int destination, int n, vector<vector<Pair>>& graphe) {
vector<int> dist(n + 1, INF);
vector<bool> visite(n + 1, false);
priority_queue<Pair, vector<Pair>, greater<Pair>> tas_min;
dist[source] = 0;
tas_min.push({0, source});
while (!tas_min.empty()) {
auto [d_actuelle, u] = tas_min.top();
tas_min.pop();
if (visite[u]) continue;
visite[u] = true;
if (u == destination) break;
for (auto [v, poids] : graphe[u]) {
if (!visite[v] && dist[v] > d_actuelle + poids) {
dist[v] = d_actuelle + poids;
tas_min.push({dist[v], v});
}
}
}
return dist[destination];
}
Variantes et etxensions
Plus long chemin
L'algorithme de Dijkstra peut être adapté pour trouver le plus long chemin dans un graphe où tous les poids sont non positifs. Dans ce cas, on initialise les distances à moins l'infini et on maximise au lieu de minimiser. Cependant, avec des poids positifs, cette adaptation échoue car la propriété de monotonie des distances n'est plus respectée, conduisant à des résultats incorrects.
