Algorytm Bellmana-Forda

Algorytm

Algorytm Bellmana-Forda służy do wyszukiwania najkrótszych ścieżek w grafie z pewnego wierzchołka do pozostałych. Krawędzie grafu mogą mieć ustalone wagi (również ujemne), ale graf nie może posiadać cykli ujemnych. Nie jest potrzebne dodatkowe sprawdzanie czy algorytm je posiada - na koniec wystarczy pętla w której zostanie określone czy cykle ujemne wystąpiły.

Algorytm

Początkowo dla każdego wierzchołka określamy, że dystans do niego jest nieskończony, a poprzednik nieokreślony z wyjątkiem wierzchołka początkowego dla którego dystans wynosi 0. Następnie należy powtórzyć n - 1 razy aktualizowanie krawędzi, gdzie n to ilość wierzchołków w grafu. Aktualizacja krawędzi polega na sprawdzeniu czy dla danej pary łączonych wierzchołków dla wierzchołka końcowego nie istnieje krótsza ścieżka tj. czy dystans wierzchołka początkowego dodany do wagi krawędzi jest mniejszy niż dystans wierzchołka końcowego. Krawędzi należy rozpatrywać w kolejności alfabetycznej.

W celu sprawdzenia czy w grafie nie ma cykli ujemnych należy dla każdej krawędzi sprawdzić czy dystans wierzchołka końcowego nie jest mniejszy od sumy dystansu wierzchołka początkowego i wagi krawędzi ich łączących. Jeśli istnieje chociaż jedna krawędź dla której nie jest to spełnione to z pewnością występują w tym grafi cykle ujemne.

Przykład

Dla przykładu na poniższym grafie zostanie wykonany algorytm Bellmana-Forda:

Przykładowy graf

Jako punkt początkowy zostaje wybrany wierzchołek A, więc dla niego na początku dystans wyniesie 0. Krawędzie będą rozpatrywane w następujące kolejności: AB, AC, AD, BD, BE, CE, DC, DE. Aktualizacja krawędzi zostanie wykonana n - 1 = 4 razy.

Teraz dla każdej krawędzi należy sprawdzić czy nie wystąpiły cykle ujemne. W tym przypadku nie jest to możliwe, ponieważ wagi krawędzi są tylko dodatnie. Ostatecznie drzewo najkrótszych krawędzi wygląda następująco:

Wynik

Implementacja

Założenia

Funkcja BellmanFord() dla podanego grafu zwróci tablicę danych z których będzie można odczytać dla każdego wierzchołka jego poprzednika oraz dystans (o ile istnieje połączenie). Algorytm nie będzie sprawdzał poprawności danych wejściowych - o tym powinien wiedzieć sam użytkownik. Graf ma zostać przekazany jako macierz. Przykładowo następujący graf:

Graf

ma zostać przekazany w programie jako następująca macierz:

1. 0 1 2 3 0
2. 0 0 0 2 4
3. 0 0 0 0 3
4. 0 0 1 0 1
5. 0 0 0 0 0

Rozwiązanie

Przechowanie danych

W celu przechowania danych utworzony zostaje specjalny typ, który dla wybranego wierzchołka pozwoli przechować jego dystans oraz poprzednika.

1. struct dane {
2.   int dystans;
3.   int poprzednik;
4. };

Algorytm

Funkcja BellmanFord() dla podanej macierzy szuka drzewa najkrótszych ścieżek od wybranego wierzchołka start. Wynikiem działania funkcji jest tablica, gdzie dla każdego wierzchołka jest określony do niego dystans oraz poprzednik. Dla przypomnienia algorytm nie sprawdza czy graf zawiera cykle ujemne.

1. dane* BellmanFord(int** macierz, int n, int start) {
2.   dane* tab = new dane[n];
3.   for (int i = 0; i < n; i++) {
4.     tab[i].dystans = INT32_MAX;
5.     tab[i].poprzednik = -1;
6.   }
7.   tab[start].dystans = 0;
8.   for (int k = 0; k < n - 1; k++) {
9.     for (int u = 0; u < n; u++) {
10.       for (int v = 0; v < n; v++) {
11.         if (macierz[u][v] != 0 &&
12.           tab[v].dystans > tab[u].dystans + macierz[u][v]) {
13.           tab[v].dystans = tab[u].dystans + macierz[u][v];
14.           tab[v].poprzednik = u;
15.         }
16.       }
17.     }
18.   }
19.   return tab;
20. }

(2. - 7.) Przygotuj tablicę do wypełnienia, a następnie (8.) powtarzając n - 1 razy i (9. - 10.) dla każdej krawędzi: (11.) sprawdź czy krawędź istnieje oraz (12.) czy trzeba zaktualizować dystans wierzchołka końcowego. Jeśli tak to (13. - 14.) należy zaktualizować dystans oraz poprzednika. Na koniec (19.) należy zwrócić wyliczoną tablicę.

Testowanie funkcji

W celu przetestowania kodu można skorzystać z poniższego fragmentu kodu. Pomocnicza funkcja wypiszDane() pozwala wyświetlić w czytelnej postaci informacje zgromadzone o wierzchołku.

1. int main() {
2.   int n, s;
3.   cout << "Ile wierzcholkow ma graf?\n n = ";
4.   cin >> n;
5.   cout << "Podaj wierzcholek poczatkowy\n s = ";
6.   cin >> s;
7.   cout << "Podaj macierz:" << endl;
8.   int** macierz = new int*[n];
9.   for (int i = 0; i < n; i++) {
10.     macierz[i] = new int[n];
11.     for (int j = 0; j < n; j++)
12.       cin >> macierz[i][j];
13.   }
14.   dane* tab = BellmanFord(macierz, n, s);
15.   cout << "Wezel\tOdl.\tPoprzednik" << endl;
16.   for (int i = 0; i < n; i++)
17.     wypiszdane(i, tab[i]);
18.   system("pause");
19.   return 0;
20. }

• Kod źródłowy Implementacja