Maxflödesalgoritmer i Java
En studie av vikten att välja rätt algoritm och datastruktur för att minimera körtiden för exakta maxflödesalgoritmer
Maxflo?desproblemet har ma?nga praktiska tilla?mpningar och probleminstanserna kan bli mycket stora. Effektiva implementationer a?r da?rfo?r no?dva?ndigt fo?r att ko?rtiden inte ska bli alltfo?r ho?g. I den ha?r studien har tva? maxflo?desalgoritmer, Edmonds-Karps algoritm och Goldberg-Tarjans push-relabel-algoritm, implementerats i Java med tva? olika da- tastrukturer och ja?mfo?rts med varandra. Det framkommer att det a?r fo?rdelaktigt att implementera en mer komplex, objektbaserad, grafre- presentation fo?r grafinstanser som ligger under en kritisk gra?ns i antal kanter. Na?r antalet kanter o?verstiger den kritiska gra?nsen blir en enkla- re, men mer minneskra?vande, implementation med grannlista av heltal tillsammans med matriser effektivare. Tyva?rr saknas tillra?cklig data fo?r att kunna dra slutsatser om huruvida Edmonds-Karps algoritm eller Goldberg-Tarjans push-relabel-algoritm a?r att fo?redra vid implementa- tion i Java.