Algoritmul Malhotra-Kumara-Maheshwari

Algoritmul Malhotra-Kumar-Maheshwari vă permite să găsiți debitul maxim într-un grafic.

Descriere

Considerăm o rețea de transport formată dintr-un graf direcționat , unde este o mulțime de vârfuri, este o mulțime de muchii și un flux . Pentru fiecare vârf se introduce un potențial de curgere egal cu debitul suplimentar maxim care poate trece prin acest vârf. Urmează ciclul. La fiecare iterație, se determină un vârf cu un potențial minim . Apoi, se începe un flux de magnitudine de la sursă la chiuvetă, trecând prin acest vârf. În acest caz, dacă capacitatea reziduală a marginii este egală cu zero, atunci această margine este eliminată. Toate vârfurile care nu au nicio margine de intrare și/sau de ieșire sunt, de asemenea, eliminate. Când un vârf este îndepărtat, toate marginile adiacente sunt eliminate. Astfel, se va găsi un flux blocant (pseudo-maxim). Pentru a găsi debitul maxim într-un grafic, trebuie să căutați un flux de blocare și apoi să modificați graficul în consecință și așa mai departe până când debitul de blocare este egal cu zero. $G=(V,\;E)$ $V$ $E$ $f$ $v\în V$ $r$ $\rho$ $\rho$

Dificultate

Dacă informațiile despre arcurile de intrare și de ieșire sunt stocate sub formă de liste legate , atunci pentru a sări peste flux, la fiecare iterație, se vor efectua acțiuni acolo unde corespunde numărului de muchii pentru care debitul rezidual a scăzut, dar a rămas pozitiv. , și la numărul de margini eliminate . Astfel, vor fi întreprinse acțiuni pentru a găsi firul de blocare. Căutarea unui fir de blocare va fi efectuată o singură dată, deoarece numărul de margini de pe calea de la sursă la scufundare într-un fir de blocare nu va scădea. Apoi totul se dovedește a fi acțiuni. $O(\left|V\right|+\left|E_{i}\right|)$ $\left|V\dreapta|$ $\left|E_{i}\right|$ $\sum _{i}{O(\left|V\right|+\left|E_{i}\right|)}=O(\left|V\right|^{2})$ $O(\stanga|V\dreapta|)$ $O(\stanga|V\dreapta|^{3})$

Literatură

Malhotra VM, Kumar M. Pramodh, Maheshwari SN Un algoritm O(IVI 3 ) pentru găsirea fluxurilor maxime în rețele . — 1978.

Algoritmul Malhotra-Kumara-Maheshwari

Descriere

Dificultate

Literatură

Note