preflowpushalgoritmer

Preflow-push-algoritmen, ofte kalt preflow-push eller push-relabel, er en familie av algoritmer for å finne maksimal flyt i rettede grafer med kapasiteter. Algoritmen ble utviklet av Andrew Goldberg og Robert Tarjan på 1980-tallet og er en av de mest effektive generelle max-flow-algoritmene i praksis. Den nyttiggjør seg av et preflow-konsept og en høydefunksjon (høyder) for å styre flyt mellom nodene.

Grunnprinsippet er å opprettholde et preflow hvor for hver node unntatt kilde og avløp er den akkumulerte flyten (overskudd) ikke negativ. Kilden får lov til å sende ut flyt som saturerer utgående kanaler. Hovedoperasjonene er push og relabel. Push flyter langs en residuell kant fra en node u til en nabo v hvis kanten har tilgang og h(u) = h(v) + 1 (admissibel kant). Relabel endrer høyden til en node når det ikke finnes noen admissible kanter, slik at en ny admissibel kant blir mulig. Prosessen fortsetter til ingen noder unntatt kilde og avløp har overskudd.

Algoritmen har flere varianter og forbedringer, blant annet global relabeling (periodisk rekonstruering av høydefordeling ved søk i residualgrafen) og gap-heuristikk (når en høyde ikke lenger har noen node, kan flere høyder elimineres for å fremskynde prosesseringen). Variasjonen FIFO eller høyeste merke kan velges som styringsregel for aktive noder.

Kompleksiteten i verste fall er O(n^3) for standard implementasjoner, men praktisk ytelse er sterk og forbedres betydelig av heuristikker. Preflow-push er velegnet for store nettverk og dynamiske inn- eller utbytter og brukes bredt i både teoretiske og anvendte max-flow-applikasjoner.