Implémentation d'algorithmes de théorie des graphes ainsi que la structure de données en C++ (cf. Network Flows, Ahuja et al)
mkdir build
cd build
cmake ..
make
./a.out
Solveurs:
./maxFlowSolver.out <PATH_TO_INSTANCE_FILE>
./minCostFlowSolver.out <PATH_TO_INSTANCE_FILE>
Projet Netflow : ici
Ce répertoire contient des programmes qui génèrent des réseaux et des graphes. La plupart sont au format DIMACS, ceci est un site Web pour en savoir plus sur ce format.
- 1 avec chemins augmantants pour flot max : successive shortest path en O(n^2m) et/ou labeling algo en O(nmU), pseudo-polynomiale --> successive shortest path -[X]
- 1 flot maximum avec pré-flots : FIFO pre-flow push algo en O(n^3) -[X]
- 1 flot de coût minimum : cycle cancelling en O(mCU), out-of-kilter en O(nu) (en priorité) et en complexité polynomiale on a le minimum mean-cycle cancelling algo en O(n^2m^3log(n)) (lui il est compliqué) --> cycle cancelling -[X]