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:

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. class dane:
2.   def __init__(self, odwiedzony, poprzednik, odl):
3.     self.odwiedzony = odwiedzony
4.     self.poprzednik = poprzednik
5.     self.odl = odl

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. def DFS(macierz, start):
2.   tab = [dane(False, -1, 0) for i in macierz]
3.   tab = odwiedzWezel(macierz, tab, start, 0)
4.   for i in range(len(macierz)):
5.     if (not tab[i].odwiedzony):
6.       tab = odwiedzWezel(macierz, tab, i, 0)
7.   return tab;

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. def odwiedzWezel(macierz, tab, u, odl):
2.   tab[u].odwiedzony = True
3.   tab[u].odl = odl
4.   for i in range(len(macierz)):
5.     if (macierz[u][i] > 0 and not tab[i].odwiedzony):
6.       tab[i].poprzednik = u
7.       tab = odwiedzWezel(macierz, tab, i, odl + 1)
8.   return tab

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. def najdluzszaSciezka(macierz):
2.   maks = 0
3.   for i in range(len(macierz)):
4.     podsumowanie = DFS(macierz, i)
5.     for j in range(len(macierz)):
6.       if (podsumowanie[j].odl > maks):
7.         maks = podsumowanie[j].odl
8.   return maks

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. n = int(input("Podaj ile jest wierzchołków w grafie\n n = "))
2. macierz = []
3. for i in range(n):
4.   macierz.append([int(x) for x in input().split()])
5. maks = najdluzszaSciezka(macierz)
6. print("Najdłuższa ściezka ma długość", maks)

• Kod źródłowy Implementacja

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

• Kod źródłowy Zadanie 1