Strona główna » Algorytmy » Artykuły » Najdłuższa Ścieżka w Grafie
 

Najdłuższa Ścieżka w Grafie

Wstęp

Do wyszukiwania najdłuższej ścieżki w grafie pomiędzy dwoma dowolnymi wierzchołkami najwygodniej zastosować odpowiednio dostosowany algorytm DFS, który będzie przechodził po węzłach i nadawał odległości. Algorytm ten zostanie wykonany dla każdego kolejnego wierzchołka w grafie. Za każdym razem algorytm DFS tworzy nową tablicę informacji z której następnie należy odczytać maksymalną odległość i porównać ją z aktualną i odpowiednio zaktualizować.

Przykład

Przypuśćmy, że dany jest następujący graf:

Przykładowy graf

Pierwszy etap polega na wykonaniu algorytmu DFS dla każdego wierzchołka w grafie. Poniższe wyniki prezentują kolejno otrzymywane wyniki:

StartABCDEFGH
A01112232
B10221343
C12023343
D12203121
E21330454
F23314032
G34425301
H23314210

Podczas działania algorytmu nie trzeba tworzyć takiej tabeli wyników. Wystarczy dla każdego kolejnego wierzchołka znaleźć maksimum i zachować jeśli jest większy od dotychczas znalezionego. W powyższym przykładzie widać, że najdłuższy odcinek jest pomiędzy wierzchołkiem G i E.

Implementacja

Przechowywanie danych

Algorytm DFS zwykle przechowuje tylko informację o wierzchołku dotyczące poprzednika oraz czy dany wierzchołek został odwiedzony. Tutaj potrzebne jest dodatkowe pole do zapamiętania odległości.

  1. struct dane {
  2.   bool odwiedzony;
  3.   int poprzednik;
  4.   int odl;
  5. };

DFS

Główna część algorytmu DFS tworzy tablicę danych, która zostanie uzupełniona przez algorytm. Działa on w pętli odwiedzając najpierw wybrany wierzchołek, a potem wszystkie pozostałe. Na koniec zwracana jest uzupełniona tablica informacji.

  1. dane* DFS(int** macierz, int n, int start) {
  2.   dane* tab = new dane[n];
  3.   for (int i = 0; i < n; i++) {
  4.     tab[i].odwiedzony = false;
  5.     tab[i].poprzednik = -1;
  6.   }
  7.   odwiedzWezel(macierz, n, tab, start, 0);
  8.   for (int i = 0; i < n; i++)
  9.     if (!tab[i].odwiedzony)
  10.       odwiedzWezel(macierz, n, tab, i, 0);
  11.   return tab;
  12. }

Do odwiedzania wierzchołków w sposób rekurencyjny została dopisana metoda odwiedzWezel(), która w momencie odwiedzenia wierzchołka przypisuje mu przekazaną odległość oraz aktualizuje, że został odwiedzony. Następnie odwiedza wszystkich jego nieodwiedzonych sąsiadów. Tu należy pamiętać, że podczas odwiedzania sąsiada odległość należy zwiększyć o 1.

  1. void odwiedzWezel(int** macierz, int n, dane* tab, int u, int odl) {
  2.   tab[u].odwiedzony = true;
  3.   tab[u].odl = odl;
  4.   for (int i = 0; i < n; i++) {
  5.     if (macierz[u][i] > 0 && !tab[i].odwiedzony) {
  6.       tab[i].poprzednik = u;
  7.       odwiedzWezel(macierz, n, tab, i, odl + 1);
  8.     }
  9.   }
  10. }

Najdłuższa ścieżka

Algorytm DFS jest gotowy do użycia, więc można teraz przejść do napisania głównej funkcji najdluzszaSciezka(), która dla danej macierzy zwróci maksymalną odległość pomiędzy wierzchołkami.

  1. int najdluzszaSciezka(int** macierz, int n) {
  2.   int maks = 0;
  3.   for (int i = 0; i < n; i++) {
  4.     dane* podsumowanie = DFS(macierz, n, i);
  5.     for (int j = 0; j < n; j++) {
  6.       if (podsumowanie[j].odl > maks) {
  7.         maks = podsumowanie[j].odl;
  8.       }
  9.     }
  10.     delete podsumowanie;
  11.   }
  12.   return maks;
  13. }

Algorytm w pętli wywołuje algorytm DFS na każdym kolejnym wierzchołku. Zwrócona tablica jest następnie analizowana w celu znalezienia większego elementu niż aktualnie znalezione maksimum. Na koniec zwracana jest znaleziona wartość.

Testowanie funkcji

Do przetestowania napisanego kodu można skorzystać z poniższego fragmentu, który wczytuje ile wierzchołków ma graf, a następnie odpowiednią macierz. Grafowi pokazywanemu wcześniej w artykule odpowiada następująca macierz:

  1. 0 1 1 1 0 0 0 0
  2. 1 0 0 0 1 0 0 0
  3. 1 0 0 0 0 0 0 0
  4. 1 0 0 0 0 1 0 1
  5. 0 1 0 0 0 0 0 0
  6. 0 0 0 1 0 0 0 0
  7. 0 0 0 0 0 0 0 1
  8. 0 0 0 1 0 0 1 0
  1. int main() {
  2.   int n;
  3.   cout << "Ile wierzcholkow ma graf?\n n = ";
  4.   cin >> n;
  5.   cout << "Podaj macierz:" << endl;
  6.   int** macierz = new int*[n];
  7.   for (int i = 0; i < n; i++) {
  8.     macierz[i] = new int[n];
  9.     for (int j = 0; j < n; j++)
  10.       cin >> macierz[i][j];
  11.   }
  12.   int maks = najdluzszaSciezka(macierz, n);
  13.   cout << "Najdlusza sciezka ma dlugosc " << maks;
  14.   system("pause");
  15.   return 0;
  16. }

Zadania

Zadanie 1

Napisz program, który dla danej macierzy znajdzie wszystkie pary wierzchołków pomiędzy, którymi odległość w grafie jest maksymalna. Przetestuj napisany program. Przykładowo dla poniższego grafu:

Przykładowy graf

algorytm powinien wypisać:

  1. Najdłuższa ściezka ma długość 5
  2. Taką długość mają ścieżki:
  3. z 4 do 6
  4. z 6 do 4