Minkapacitetsalgoritmer

Minkapacitetsalgoritmer er en klasse av algoritmer innenfor datalogi som har som mål å finne en maksimal strømning i et nettverk. Et nettverk består typisk av en kilde, en sluk, og en rekke noder forbundet med kanter. Hver kant har en kapasitet, som representerer den maksimale mengden "stoff" som kan flyte gjennom den. Målet med en minkapacitetsalgoritme er å finne den største totale mengden som kan flyte fra kilden til sluket, uten at kapasiteten til noen kant overskrides.

Disse algoritmene fungerer ved gjentatte ganger å finne "forbedringsstier" i nettverket. En forbedringssti er en vei fra kilden til sluket der det fortsatt er ledig kapasitet. Algoritmen øker deretter strømningen langs denne stien med den minst ledige kapasiteten på stien. Denne prosessen gjentas til ingen flere forbedringsstier kan finnes. Når dette skjer, har en maksimal strømning blitt oppnådd.

Det finnes flere kjente minkapacitetsalgoritmer, inkludert Ford-Fulkerson-algoritmen og Edmonds-Karp-algoritmen. Edmonds-Karp er en spesifikk implementasjon av Ford-Fulkerson som bruker bredde-først-søk (BFS) for å finne de korteste forbedringsstiene. Dette garanterer at algoritmen terminerer og gir en effektiv løsning for mange typer nettverk. Minkapacitetsalgoritmer har anvendelser innenfor områder som transportlogistikk, ressursallokering, nettverksruting og planlegging.