Programmation dynamique : Algorithmes des voies les plus courtes

Cette séance de cours couvre les stratégies de programmation dynamique pour la résolution de problèmes, en mettant l'accent sur les algorithmes pour trouver les chemins les plus courts. Il commence par tabuler des valeurs déjà calculées, illustrées par le triangle de Pascal. Ensuite, il introduit l'algorithme Floyd pour calculer le trajet le plus court entre toutes les gares du réseau CFF. La séance de cours explique l'algorithme étape par étape, mettant l'accent sur le concept de programmation dynamique. Il traite également de la complexité de l'algorithme et de son application aux réseaux avec n nœuds. De plus, il mentionne d'autres algorithmes liés à la recherche des chemins les plus courts, comme l'algorithme de Dijkstra, A* et Viterbi. La séance de cours conclut en soulignant la variété des algorithmes disponibles sur la base de conditions graphiques spécifiques.