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.   public bool odwiedzony;
  3.   public int poprzednik;
  4.   public 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. static dane[] DFS(int[,] macierz, int start) {
  2.   dane[] tab = new dane[macierz.GetLength(0)];
  3.   for (int i = 0; i < macierz.GetLength(0); i++) {
  4.     tab[i].odwiedzony = false;
  5.     tab[i].poprzednik = -1;
  6.   }
  7.   odwiedzWezel(macierz, ref tab, start, 0);
  8.   for (int i = 0; i < macierz.GetLength(0); i++)
  9.     if (!tab[i].odwiedzony)
  10.       odwiedzWezel(macierz, ref 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. static void odwiedzWezel(int[,] macierz, ref dane[] tab, int u, int odl) {
  2.   tab[u].odwiedzony = true;
  3.   tab[u].odl = odl;
  4.   for (int i = 0; i < macierz.GetLength(0); i++) {
  5.     if (macierz[u, i] > 0 && !tab[i].odwiedzony) {
  6.       tab[i].poprzednik = u;
  7.       odwiedzWezel(macierz, ref 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. static int najdluzszaSciezka(int[,] macierz) {
  2.   int maks = 0;
  3.   for (int i = 0; i < macierz.GetLength(0); i++) {
  4.     dane[] podsumowanie = DFS(macierz, i);
  5.     for (int j = 0; j < macierz.GetLength(0); j++) {
  6.       if (podsumowanie[j].odl > maks) {
  7.         maks = podsumowanie[j].odl;
  8.       }
  9.     }
  10.   }
  11.   return maks;
  12. }

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. static void Main(string[] args) {
  2.   Console.Write("Podaj ile jest wierzchołków w grafie\n n = ");
  3.   int n = Convert.ToInt32(Console.ReadLine());
  4.   int[,] macierz = new int[n, n];
  5.   for (int i = 0; i < n; i++) {
  6.     string[] str = Console.ReadLine().Split(' ');
  7.     for (int j = 0; j < n; j++) {
  8.       macierz[i, j] = Convert.ToInt32(str[j]);
  9.     }
  10.   }
  11.   int maks = najdluzszaSciezka(macierz);
  12.   Console.WriteLine("Najdłuższa ściezka ma długość {0}", maks);
  13.   Console.ReadKey();
  14. }

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