Flux maxim de cost minim

[tmac]

cum se face ... ?

[ditzone]

Asemanator fluxului normal, doar ca ai grija la fiecare pas drumul de la sursa la destinatie sa aibe cost minim. In loc de o simpla parcurgere in latime sau adancime faci un bellman ford..

[u-92]

cand gasesti un flux admisibil il faci si de cost minim. o sa ai cost(i,j) = costul pe arcul (i->j) iar cost(j,i) = -cost(i,j)
Acum poti sa demonstrezi ca atata timp cat exista un ciclu negativ in graful asta poti obtine un cost mai bun adaugand pe fiecare muchie din ciclu o cantintate de flux egala cu minimul fluxului de pe toate muchiile din ciclu.

[tmac]

am inteles. ms mult ! 

[tmac]

nu pot sa fac dijsktra in loc de bellman ford ? parcurgerea in latime gaseste un cel mai scurt drum relativ la nr de muchii, dijsktra gaseste un cel mai scurt drum relativ la costurile pe muchii. sau fac bellman ford acela cu coada sa optimizez si un flux maxim si un cost minim ?
 

[•wefgef]

nu poti sa faci dijkstra pentru ca pe muchiile de intoarcere vei avea cost negativ.

[tmac]

se pare ca nu stiu exact formularea problemei . Poatemi spune cineva exact formularea ...

[•Marius]

cand gasesti un flux admisibil il faci si de cost minim. o sa ai cost(i,j) = costul pe arcul (i->j) iar cost(j,i) = -cost(i,j)
Acum poti sa demonstrezi ca atata timp cat exista un ciclu negativ in graful asta poti obtine un cost mai bun adaugand pe fiecare muchie din ciclu o cantintate de flux egala cu minimul fluxului de pe toate muchiile din ciclu.

Acel drum de cost minim se bazeaza pe muchiile capacitate - flux, adica capacitate reziduala ?
De ce cost(j, i) = - cost(i, j) ?
De pe acel drum minim aleg muchia cu capacitatea reziduala minima si adun la fluxul muchiilor ?
Exista undeva in lume niste demonstratii pentru cele zise mai sus, sa contrazica intuitia ?

[•cristy]

uita-te in Cormen

[•Marius]

Introducere in Algoritmi imi raspunde la intrebarile de mai sus despre flux maxim de COST MINIM ?
Nu zic ca nu e, dar eu nu am gasit... 

[•byndrsn]

nu pot sa fac dijsktra in loc de bellman ford ? parcurgerea in latime gaseste un cel mai scurt drum relativ la nr de muchii, dijsktra gaseste un cel mai scurt drum relativ la costurile pe muchii. 

.

. poti sa folosesti Dijkstra daca nu ai cicluri de cost negativ, dar trebuie sa modifici
greutatile pe muchii ca sa devina non-negative...

pentru a modifica greutatile muchiilor, tii un vector f[ v ] = potentialul varfului v
greutatea (costul) fiecarei muchii e = u->v devine w[ e ] + f[ u ] - f[ v ], unde w[ e ] este adevaratul cost al muchiei...
costul unui drum de la s la t se modifica cu o constanta (f[ s ] - f[ t ]), asa ca drumurile de cost minim in graful cu
costurile modificate nu se modifica..

initial f[ v ] = costul minim de la s la v
noul cost al unei muchii e >= 0, pentru orice muchie e = u->v (pentru ca alfel ai avea f[ v ] > f[ u ] + w[ e ],
ceea ce contrazice faptul ca f[ v ] este costul minim)

tot ceea ce ramane de facut e sa modifici potentialele de fiecare data cand
gasesti un augmenting path (trebuie sa le modifici inainte sa trimiti flux
pe drumul gasit)...

sa zicem ca ai gasit un augmenting path p folosind Dijkstra, si d[ v ] = costul
minim de la s la v (gasit de Dijkstra la pasul curent)..
vrei sa modifici potentialele inainte sa trimiti flux pe drumul p astfel incat
toate muchiile pe drumul p sa aiba noul cost 0 (astfel muchiile de intoarcere vor
avea si ele noul cost 0)

asa ca faci update astfel: f[ v ] <- f[ v ] + d[ v ]

teoretic, implementarea naiva max flow + Bellman Ford e O(n^4), si max flow +
Dijkstra + costuri modificate e O(n^3)..
practic, nu stiu care e mai rapid...

[•azotlichid]

Inteligent  Auzisem ca se poate folosi Dijkstra pt flux maxim de cost minim, totusi nu am cautat niciodata o imbunatatire fata de vechiul Bellman Ford  Banuiesc ca ideea de modificare a greutatilor muchiilor are niste aplicatii foarte interesante si in alte probleme...

[•Cosmin]

Cica nu ajuta sensibil ca timp sa folosesti Dijkstra in loc de Bellman Ford.

[•azotlichid]

Asta in practica Dar teoria ascunde inca multe idei elegante 

[•Marius]

Ce complexitate are algoritmul Ungar ? 

[VladS]

O( N ^ 3 )