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 prezentat in aceasta problema este necesar pentru a rezolva mai multe probleme de informatica, cum ar fi:

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:

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