Dijkstra : plus court chemin pondéré
AvancéAvec des poids positifs sur les arêtes, on développe toujours le sommet le plus proche non encore finalisé, grâce à un heap.
BFS ne suffit plus dès que les arêtes ont un coût. Dijkstra maintient la meilleure distance connue vers chaque sommet et extrait à chaque tour, du heap, le sommet de distance minimale. Complexité O((V + E) log V).
Piège : Dijkstra est faux avec des poids négatifs. Dans ce cas, utilisez Bellman-Ford (O(V × E)). Avec un poids uniforme (tous à 1), un simple BFS suffit.
Le graphe est une liste d'adjacence de paires (voisin, poids).
// Utilise une file de priorité de paires [distance, sommet] : voir MinHeap dans la leçon « Heap ».
// Ici, un mini-heap générique trié sur le premier élément de la paire.
class PairHeap {
private a: [number, number][] = [];
get size() { return this.a.length; }
push(x: [number, number]): void {
const a = this.a;
a.push(x);
let i = a.length - 1;
while (i > 0 && a[(i - 1) >> 1][0] > a[i][0]) {
[a[(i - 1) >> 1], a[i]] = [a[i], a[(i - 1) >> 1]];
i = (i - 1) >> 1;
}
}
pop(): [number, number] {
const a = this.a;
const top = a[0];
const last = a.pop()!;
if (a.length) {
a[0] = last;
let i = 0;
for (;;) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && a[l][0] < a[m][0]) m = l;
if (r < a.length && a[r][0] < a[m][0]) m = r;
if (m === i) break;
[a[m], a[i]] = [a[i], a[m]];
i = m;
}
}
return top;
}
}
function dijkstra(graph: [number, number][][], source: number): number[] {
const dist = new Array<number>(graph.length).fill(Infinity);
dist[source] = 0;
const heap = new PairHeap();
heap.push([0, source]);
while (heap.size) {
const [d, u] = heap.pop();
if (d > dist[u]) continue; // entrée périmée : déjà mieux connue
for (const [v, w] of graph[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
heap.push([dist[v], v]);
}
}
}
return dist;
}
Astuce : en C, on réutilise le min-heap de la leçon « Heap » en y stockant des paires (distance, sommet). Pour un graphe pondéré très dense, la version O(V²) sans heap peut être plus simple et aussi rapide.