Flusso massimo con algoritmo Edmonds - Karp
-
03-11-2019 - |
Domanda
Sto imparando l'algoritmo Edmonds - Karp, ho formato seguendo la rete di flusso (la capacità è descritta sopra freccia, dove s è sorgente e t è affascinante.)
Se seguiamo per la prima volta il percorso S - a - c - t , otterremo il flusso massimo equivale a 1 in quanto non possiamo prendere il percorso s - b - c - t (flusso residuo da c - t è diventato 0). Suppongo anche che mentre facciamo BFS quando raggiungiamo T da C, stiamo fermando la nostra ricerca BFS e il percorso di ritorno. È rimasto D in coda, ma lo ignoreremo perché abbiamo un percorso di aumento. Alla prossima iterazione passeremo a B come s - una capacità residua a bordo è 0.
Se seguiamo per la prima volta il percorso come S - a - d - t poi S - b - c - t , otteniamo un flusso massimo come 2.
Penso che mi mancano alcune basi, credo che l'algoritmo non dipenda dal percorso che prendo per primo.
Grazie in anticipo.
Nessuna soluzione corretta