Algorithme de Dijkstra
Plus court chemin pondéré
Enonce
G = {0:[(1,4),(2,1)], 1:[(3,1)], 2:[(1,2),(3,5)], 3:[]}
Implémenter dijkstra(G, source) → dict des distances minimales.
Signature attendue
def dijkstra(G: dict, source: int) -> dict:📖 Rappel de cours
Invariant :
Tout sommet extrait du tas a sa distance définitive.
$O\bigl((|V|+|E|)\log|V|\bigr)$
⚠ Le piège : L'algorithme suppose des poids positifs : avec une arête négative, un sommet déjà extrait pourrait être amélioré plus tard, et l'invariant tombe. Dans ce cas il faut Bellman-Ford. Réciproquement, sur un graphe non pondéré, un simple parcours en largeur suffit et coûte moins cher.
← Exercices sur les graphes en Python — BFS, DFS, Dijkstra
Exercices du meme theme
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.