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

Acest algoritm 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.

Acest algoritm 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, pentru a determina cuplajul de cost maxim intr-un graf biparit, folosim 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