Implémentation de l’algorithme du plus court chemin successif (Successive Shortest Path) à partir de zéro, incluant la construction du graphe résiduel, l’extraction de chemins de coût minimal basée sur Bellman–Ford et la logique d’augmentation de flot.
Conception et réalisation d’une évaluation expérimentale à grande échelle sur des graphes euclidiens orientés aléatoires selon 28 configurations, avec variation de la densité (𝑟), des bornes de capacité et des régimes de coûts.
Comparaison des algorithmes SSP, mise à l’échelle des capacités (Capacity Scaling), Scaling-SSP et primal–dual à l’aide de métriques incluant le coût total, la valeur du flot, le nombre de chemins augmentants, la longueur moyenne des chemins et la longueur proportionnelle des chemins.
Mise en évidence que l’algorithme primal–dual atteint systématiquement le coût minimal optimal, tandis que SSP offre des performances compétitives dans des régimes clairsemés et se dégrade dans les graphes denses.
