42. Algorithme de Dijkstra : Introduction et Avidité (Greediness)

L'Algorithme de Dijkstra résout le problème du plus court chemin à source unique pour un graphe pondéré avec des poids d'arête non négatifs.

Concept de Base : Approche Greedy

Dijkstra's est un Algorithme Glouton (Greedy Algorithm). À chaque étape, il fait le choix qui semble le meilleur pour le moment, dans l'espoir que cet optimum local mènera à un optimum global.

1. Commencer au nœud source, en définissant sa distance à 0 et toutes les autres à l'infini.
2. Sélectionner à plusieurs reprises le nœud non visité qui a actuellement la plus petite distance connue à partir de la source.
3. « Visiter » ce nœud et mettre à jour les distances de tous ses voisins.

Exigence de Structure de Données

Dijkstra's utilise un Min Heap (File de Priorité) pour trouver efficacement le nœud non visité avec la plus petite distance en temps O(log N), rendant la complexité globale très efficace.