Spingi Relabel perché tornare alla fonte
-
03-11-2019 - |
Domanda
Nell'algoritmo Push Relabel, all'estremità in eccesso in qualsiasi nodi viene spinto alla sorgente sollevando l'altezza di quei nodi sopra l'altezza della sorgente. Perché è fatto? In CLRS è menzionato:
Per rendere il preflusso un flusso "legale", l'algoritmo invia quindi l'eccesso raccolto nei serbatoi di vertici traboccanti alla fonte continuando a rielaborare i vertici su al di sopra dell'altezza fissa | V | della fonte. Come vedremo, una volta che avremo svuotato tutti i bacini idrici, il preflusso non è solo un flusso "legale", ma è anche un flusso massimo.
Cosa significa dire "rendere preflow un flusso legale". Qualcuno potrebbe approfondire lo stesso.
Nessuna soluzione corretta
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange