Dans le tournoi final, il y aura de la boue dans le labyrinthe, c’est à dire des cases adjacentes pour lesquelles aller de l’une à l’autre prendra plus d’un mouvement. Si la notion de graphe pondéré ne vous vient pas immédiatement à l’esprit, nous vous conseillons de relire ce paragraphe.
Dans ce cours, nous présentons deux nouveaux algorithmes pour parcourir des graphes pondérés et déterminer les plus courts chemins entre des sommets. L’un de ces algorithmes (Dijkstra) utilise une structure de données un peu particulière que nous étudions en détails : le tas-min.
Ces deux algorithmes ont un même but (trouver le plus court chemin entre deux nœuds), mais ne sont pas identiques. Rappelez vous que nous avons vu dans le cours 2 un outil formel permettant de les comparer : la complexité.
Articles à étudier
- La complexité des algorithmes (encore !)
- Les files de priorité
- L’algorithme de Dijkstra
- L’algorithme de Floyd-Warshall