MP, PSI et la TSI
Les graphes
Programmation dynamique
Premium
plus cours chemin dans un graphe
Chemin
bellman-ford
Dijkstra
plus court chemin
Plus courts chemins entre toutes les paires de sommets dans un graphe orienté et pondéré - Algorithme Floyd-Warshall
L'algorithme de Floyd-Warshall change de paradigme. Son objectif est de calculer simultanément les distances minimales pour tous les couples de sommets \((i,j)\). C'est un outil indispensable pour l'analyse de réseaux denses (où le nombre d'arêtes \(A\) est proche de \(S^2\)) et pour la détection de structures pathologiques comme les cycles de poids négatifs.