43. Algorithme de Dijkstra : Étapes d'Implémentation Détaillées

Formalisons les étapes pour Dijkstra's :

1. Initialisation : Créer un tableau de distance dist (tous définis à l'infini, source définie à 0) et un ensemble visited (vide).
2. Configuration de la File de Priorité : Insérer le nœud source (distance 0) dans un Min Heap.
3. Itération : Tant que le Min Heap n'est pas vide : a. Extraire le nœud U avec la distance minimale (l'étape gloutonne). b. Si U a déjà été traité (dans l'ensemble visited), continuer. c. Marquer U comme visité. d. Relaxation : Pour chaque voisin V de U : * Calculer la nouvelle distance provisoire : new_dist = dist[U] + weight(U, V). * Si new_dist < dist[V], mettre à jour dist[V] à new_dist et insérer/mettre à jour V dans la file de priorité.

• Complexité : Avec un tas de Fibonacci, O(E + V log V). Avec un Binary Heap standard (plus courant), O((V + E) log V).