Logo
Wydrukuj tę stronę

Algorytm forda - fulkersona i jego znaczenie w rozwiązywaniu problemów transportowych

Artykuł zawiera autorski program Pgraf.exe, w którym zaimplementowano algorytm Forda Fulkersona. Obliczenia wykonywane ręcznie wg tego algorytmu są czasochłonne, zatem opracowany program pozwala zaoszczędzić czas. Zapewnia również możliwość przechowywania w pamięci raz wprowadzonego grafu. Może mieć on zastosowanie w wielu dziedzinach, chociażby w logistyce.
WPROWADZENIE
Celem artykułu jest prezentacja algorytmu Forda - Fulkersona. Idea algorytmu została w nim wyjaśniona na przykładzie praktycznym dzięki sformułowaniu tzw. studium przypadku. Zwrócono uwagę na znaczenie tego algorytmu w rozwiązywaniu problemów transportowych, jak również zaprezentowano zaprojektowane autorskie oprogramowanie
Algorytmu Forda - Fulkersona. Przedstawiony w artykule program Pgraf.exe napisany został z wykorzystaniem języka C++. Jeden z rozdziałów opisuje sposób pisania i etapy projektowania tego programu. Zaprezentowany własny program Pgraf.exe jest prostszy w obsłudze, bardziej wydajny oraz posiada bardziej przyjazny interfejs graficzny od istniejących na rynku rozwiązań.
1. ISTOTA ALGORYTMU FORDA FULKERSONA
Algorytm Forda- Fulkersona opiera się na twierdzeniu o maksymalnym przepływie i minimalnym przekroju. Wynik ten został po raz pierwszy udowodniony przez Forda
Fulkersona w 1955 roku. Twierdzenie to dowodzi, że wartość dowolnego przepływu maksymalnego jest równa przepustowości dowolnego przekroju minimalnego. Stosowanie go opiera się na poszukiwaniu takiego przekroju i przepływu, że wartość przepływu jest równa przepustowości przekroju.
Algorytm w ujęciu ilościowym można najprościej określić jako pewnego rodzaju receptę, która pomoże rozwiązać pewien problem matematyczny. Składa się ze zbioru wskazówek, które mają być pomocne w rozwiązaniu danego zagadnienia. Każdy krok w takim algorytmie musi być określony w sposób precyzyjny i jednoznaczny, a proces ma zakończenie po skończonej liczbie kroków.
(...)
© 2000-2023 Sieć Badawcza Łukasiewicz - Poznański Instytut Technologiczny