Pentru a imbunatati algoritmul de mai sus, atunci cand cautam drumul de ameliorare de cost minim putem folosi si 'algoritmul lui Dijkstra':problema/dijkstra, dar inainte graful trebuie modificat astfel incat sa nu mai exista arce cu cost negativ. Definim $Dist{~i~}$ ca fiind distanta minima de la $S$ la nodul $i$. Initial, folosind algoritmul lui Bellman-Ford, calculam valorile vectorului $Dist$. Apoi, fiecarui arc {$x->y$} de cost $z$ i se va asocia costul $z + Dist{~x~} - Dist{~y~}$. Costul arcelor devine pozitiv, altfel ar insemna ca $Dist{~x~} + z < Dist{~y~}$, ceea ce ar contrazice minimalitatea lui $Dist{~y~}$. Costul drumurilor minime difera fata de cele initale printr-o constanta, deci transformarea modifica doar costul acestora si nu le schimba cu alte drumuri. In consecinta, la fiecare pas vom putea folosi algorimul lui Dijkstra pentru a determina drumul de ameliorare si vom putea folosi distantele calculate cu acest algoritm pentru a modifica din nou costurile arcelor. Algoritmul lui Dijkstra are complexitate $O(M*logN)$, deci complexitatea totala devine $O(N*M^2^*logN)$, dar este iarasi supraestimata. Aceasta rezolvare obtine $100$ de puncte, iar o sursa demonstrativa se gaseste 'aici':job_detail/238424?action=view-source.

Algoritmul de flux maxim si cost minim poate fi aplicat si pentru grafuri neorientate cu modificari minime. In plus, poate fi aplicat si pentru determinarea cuplajului de cost minim intr-un graf bipartit. De asemenea, putem determina si cuplajul de cost maxim intr-un graf biparit, folosind acelasi algoritm dupa ce costul fiecarei muchii a fost inlocuit cu diferenta dintre valoarea maxima a unei muchii si valoarea curenta. In acest caz, rezultatul va fi egal cu diferenta dintre produsul fluxului si valoarea maxima a unei muchii si costul fluxului obtinut pe graful modificat.
 

h2. Aplicatii

Algoritmul de flux maxim si cost minim poate fi aplicat si pentru grafuri neorientate cu modificari minime. In plus, poate fi aplicat si pentru determinarea cuplajului de cost minim intr-un graf bipartit. De asemenea, putem determina si cuplajul de cost maxim intr-un graf biparit, folosind acelasi algoritm dupa ce costul fiecarei muchii a fost inlocuit cu diferenta dintre valoarea maxima a unei muchii si valoarea curenta. In acest caz, rezultatul va fi egal cu diferenta dintre produsul fluxului si valoarea maxima a unei muchii si costul fluxului obtinut pe graful modificat.
Rezolvarea urmatoarelor probleme foloseste ideile de mai sus:

Algoritmul prezentat in aceasta problema este necesar pentru a rezolva mai multe probleme de informatica, cum ar fi:

* 'Cc':problema/cc
* 'Traseu':problema/traseu