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
scroll top