41. Graphes Pondérés et Problème du Plus Court Chemin

Dans de nombreux scénarios du monde réel, les arêtes d'un graphe ont des coûts associés (poids). Le Problème du Plus Court Chemin est crucial ici.

Définition

Étant donné un graphe pondéré et un nœud source S, le but est de trouver le chemin de S à tous les autres nœuds V tel que la somme des poids le long de ce chemin soit minimisée.

Pourquoi le BFS Échoue Ici

Rappelez-vous, le BFS trouve le chemin le plus court en termes de nombre d'arêtes. Dans un graphe pondéré, avoir moins d'arêtes ne signifie pas que le chemin est « plus court » (moins coûteux). Un chemin avec 3 arêtes courtes pourrait être moins cher qu'un chemin avec 2 très longues arêtes.

Nous avons besoin d'algorithmes spécialisés qui tiennent compte des poids, tels que l'algorithme de Dijkstra.