Jak znaleźć „trasy” najkrótszych ścieżek dla wszystkich par za pomocą algorytmu Floyda-Warshalla w języku C#

Wstęp

W poprzednim poście zobaczyliśmy, jak rozwiązać problem najkrótszej ścieżki dla wszystkich par, używając . Zbadaliśmy również kilka sposobów na poprawę wydajności algorytmu, używając paralelizmu i wektoryzacji.

Jednakże, jeśli pomyślimy o wynikach algorytmu Floyda-Warshalla, szybko zauważymy interesujący moment – znamy odległości (wartości najkrótszych ścieżek) między wierzchołkami w grafie, ale nie znamy „tras”, tzn. nie wiemy, jakie wierzchołki przyczyniają się do każdej najkrótszej ścieżki i nie możemy odtworzyć tych „tras” na podstawie posiadanych wyników.

W tym poście zapraszam do dołączenia do mnie i rozszerzenia algorytmu Floyda-Warshalla. Tym razem upewnimy się, że możemy obliczyć odległość i odbudować „trasę”.

Trochę znanej teorii…

Zanim zagłębimy się w kod i testy porównawcze, przypomnijmy sobie teorię działania algorytmu Floyda-Warshalla.

Oto opis tekstowy algorytmu:

1. Zaczynamy od przedstawienia grafu ( G ) o rozmiarze N jako macierzy ( W ) o rozmiarze N x N , gdzie każda komórka W[i,j] zawiera wagę krawędzi od wierzchołka i do wierzchołka j (patrz Rysunek 1). W przypadkach, gdy nie ma krawędzi między wierzchołkami, komórka jest ustawiana na specjalną wartość NO_EDGE (pokazaną jako ciemne komórki na Rysunku 1).

   
   

2. Od tej chwili mówimy – W[i,j] zawiera odległość między wierzchołkami i oraz j .

   
   

3. Następnie bierzemy wierzchołek k i przechodzimy przez wszystkie pary wierzchołków W[i,j] sprawdzając czy odległość i ⭢ k ⭢ j jest mniejsza niż aktualnie znana odległość między i i j .

   
   

4. Najmniejsza wartość jest przechowywana w W[i,j] , a krok nr 3 jest powtarzany dla następnego k aż wszystkie wierzchołki G zostaną użyte jako k .

Oto pseudo-kod:

 algorithm FloydWarshall(W) do for k = 0 to N - 1 do for i = 0 to N - 1 do for j = 0 to N - 1 do W[i,j] = min(W[i,j], W[i,k] + W[k,j]) end for end for end for end algorithm

Po wykonaniu tej operacji każda komórka W[i,j] macierzy W będzie zawierała odległość najkrótszej ścieżki między wierzchołkami i i j lub wartość NO_EDGE , jeśli nie ma między nimi ścieżki.

Jak wspomniałem na początku – posiadanie tylko tych informacji uniemożliwia rekonstrukcję tras między tymi wierzchołkami. Więc… co powinniśmy zrobić, aby móc zrekonstruować te trasy?

Cóż... może to zabrzmieć oczywiste, ale... musimy zebrać więcej danych!

… Trochę tej samej teorii, ale z innej perspektywy

Istotą algorytmu Floyda-Warshalla jest przedział o znanej odległości W[i,j] z odległością potencjalnie nowej ścieżki z i do j przez wierzchołek pośredni k .

Przywiązuję tak dużą wagę do tego szczegółu, ponieważ jest on kluczem do tego, jak możemy zachować informacje o trasie. Weźmy poprzedni graf 5 wierzchołków (patrz Rysunek 2) i wykonajmy na nim algorytm Floyda-Warshalla.

Początkowo znamy wszystkie krawędzie grafu, co daje nam następujące ścieżki: 0 ⭢ 1 :2 , 0 ⭢ 4 :10 , 1 ⭢ 3 :1 , 2 ⭢ 4 :1 , 3 ⭢ 2 :1 i 3 ⭢ 4 :3 .

Wiemy również, że nie ma krawędzi prowadzących do wierzchołka 0 , więc wykonywanie algorytmu dla k = 0 nie ma sensu. Oczywiste jest również, że istnieje pojedyncza krawędź ( 0 ⭢ 1 ) prowadząca od wierzchołka 0 do wierzchołka 1 , co również sprawia, że wykonywanie wszystkich i != 0 ( i jest tutaj „z”) jest całkowicie bezsensowne, a ponieważ wierzchołek 1 ma krawędzie z 2 i 4 , nie ma również sensu wykonywanie algorytmów dla dowolnego j , które nie jest 2 lub 4 ( j jest tutaj „do”).

Dlatego naszym pierwszym krokiem będzie wykonanie algorytmu dla k = 1 , i = 0 i j = 2,4 .

Krok	Ścieżka	Komentarz
1	0 ⭢ 1 ⭢ 2	Znaleziono ścieżkę. Odległość = 3 (nie było nic)
2	0 ⭢ 1 ⭢ 4	Znaleziono ścieżkę. Odległość = 8 (było 10).

Znaleźliśmy dwie ścieżki: nową ścieżkę ( 0 ⭢ 1 ⭢ 2 ) i skrót ( 0 ⭢ 1 ⭢ 4 ). Obie przechodzą przez wierzchołek 1 Jeśli nie zapiszemy tej informacji (faktu, że dotarliśmy do 2 i 4 przez 1 ) gdzieś teraz, zostanie ona utracona na zawsze (a to jest całkowite przeciwieństwo tego, czego chcemy).

Co więc powinniśmy zrobić? Zaktualizujemy macierz W nowymi wartościami (patrz Rysunek 3a) i zapiszemy wartość k ( k = 1 ) w komórkach R[0,2] i R[0,4] nowej macierzy R o takim samym rozmiarze jak macierz W ale zainicjowanej wartościami NO_EDGE (patrz Rysunek 3b).

Na razie nie skupiajmy się na tym, czym dokładnie jest macierz R Po prostu kontynuujmy i wykonajmy algorytm dla następnego k = 2 .

Tutaj wykonamy tę samą analizę (aby zrozumieć, jakie kombinacje mają sens wykonać), jaką przeprowadziliśmy dla k = 1, ale tym razem użyjemy macierzy W zamiast wykresu G Przyjrzyjmy się macierzy W , szczególnie w kolumnie nr 2 i wierszu nr 2 (Rysunek 4).

Tutaj widać, że istnieją dwie ścieżki do wierzchołka 2 z wierzchołka 0 i z wierzchołka 1 (kolumna nr 2) oraz dwie ścieżki z wierzchołka 2 do wierzchołka 3 i do wierzchołka 4 (wiersz nr 2). Wiedząc o tym, ma sens wykonanie algorytmu tylko dla kombinacji k = 2 , i = 0,1 i j = 3,4 .

Krok	Ścieżka	Komentarz
1	0 ⭢ 2 ⭢ 3	Znaleziono ścieżkę. Odległość = 4 (było nic)
2	0 ⭢ 2 ⭢ 4	Znaleziono ścieżkę. Odległość = 6 (było 8)
3	1 ⭢ 2 ⭢ 3	Znaleziono ścieżkę. Odległość = 2 (nie było nic)
4	1 ⭢ 2 ⭢ 4	Znaleziono ścieżkę. Odległość = 4 (było 6)

Jak już zrobiliśmy wcześniej, aktualizujemy komórki W[0,3] , W[0,4] , W[1,3] , W[1,4] o nowe odległości, a komórki R[0,3] , R[0,4] , R[1,3] i R[1,4] o k = 2 (patrz Rysunek 5).

Pozostało tylko k = 3 do przetworzenia (ponieważ nie ma krawędzi prowadzących z wierzchołka 4 do żadnego innego wierzchołka na grafie).

Przyjrzyjmy się ponownie macierzy W (rysunek 6).

Zgodnie z macierzą W istnieją trzy ścieżki do wierzchołka 3 z wierzchołków 0 , 1 i 2 (kolumna nr 3), a istnieje jedna ścieżka z wierzchołka 3 do wierzchołka 4 (wiersz nr 3). Dlatego mamy następujące ścieżki do przetworzenia:

Krok	Ścieżka	Komentarz
1	0 ⭢ 3 ⭢ 4	Znaleziono ścieżkę. Odległość = 5 (było 6)
2	1 ⭢ 3 ⭢ 4	Znaleziono ścieżkę. Odległość = 3 (było 4)
3	2 ⭢ 3 ⭢ 4	Znaleziono ścieżkę. Odległość = 2 (było 3)

Była to ostatnia iteracja algorytmu. Pozostało jedynie zaktualizować komórki W[0,4] , W[1,4] , W[2,4] nowymi odległościami i ustawić komórki R[0,4] , R[1,4] , R[2,4] na 3 .

Oto co otrzymaliśmy na końcu algorytmu (Rysunek 7).

Jak wiemy z poprzedniego wpisu , macierz W zawiera teraz wszystkie pary najkrótszych ścieżek w grafie G Ale co jest przechowywane w macierzy R ?

Powrót

Za każdym razem, gdy znaleźliśmy nową najkrótszą ścieżkę, aktualizowaliśmy odpowiadającą jej komórkę macierzy R bieżącą wartością k . Podczas gdy na początku ta czynność może wydawać się tajemnicza, ma ona bardzo proste znaczenie – przechowywaliśmy wierzchołek, z którego dotarliśmy do wierzchołka docelowego: i ⭢ k ⭢ j (tutaj docieramy do j bezpośrednio z k ).

Ten moment jest kluczowy. Ponieważ znajomość wierzchołka, z którego przyszliśmy, pozwala nam na odbudowanie trasy poprzez cofanie się (jak homar) od wierzchołka j („do”) do wierzchołka i („od”).

Poniżej znajduje się opis tekstowy algorytmu przebudowującego trasę z i do j :

1. Przygotuj pustą tablicę dynamiczną X
2. Zacznij od odczytania wartości z z komórki R[i,j] .
3. Jeśli z jest NO_EDGE , to trasa z i do j została znaleziona i możemy przejść do kroku nr 7.
4. Dodaj z na początku tablicy dynamicznej X
5. Odczytaj wartość komórki R[i,z] do z .
6. Powtarzaj kroki 3, 4 i 5, aż zostanie osiągnięty warunek wyjścia podany w punkcie 3.
7. Dodaj i do X.
8. Dodaj j do X
9. Teraz dynamiczna tablica X zawiera trasę z i do j .

W pseudokodzie wygląda to jeszcze prościej:

 algorithm RebuildRoute(i, j, R) x = array() z = R[i,j] while (z ne NO_EDGE) do x.prepend(z) z = R[i,z] end while x.prepend(i) x.append(j) return x end algorithm

Wypróbujmy to na naszym grafie G i odbudujmy trasę od wierzchołka 0 do wierzchołka 4 (patrz rysunek 8).

Oto opis tekstowy powyższej ilustracji:

1. Zaczynamy od odczytania wartości z R[0,4] , co daje wynik 3 Zgodnie z algorytmem oznacza to, że trasa prowadzi do wierzchołka 4 z wierzchołka 3 (zaznaczonego na NIEBIESKO).

   
   

2. Ponieważ wartość R[0,4] nie jest równa NO_EDGE , kontynuujemy i odczytujemy wartość R[0,3] co daje wynik 2 (zaznaczony na ZIELONO).

   
   

3. Ponownie, ponieważ wartość R[0,3] nie jest NO_EDGE , kontynuujemy i odczytujemy wartość R[0,2] co daje wynik 1 (zaznaczony na CZERWONO).

   
   

4. Na koniec odczytujemy wartość R[0,1] , co skutkuje wartością NO_EDGE , co oznacza, że nie ma więcej wierzchołków poza 0 i 4 , które przyczyniają się do trasy. Dlatego wynikowa trasa to: 0 ⭢ 1 ⭢ 2 ⭢ 3 ⭢ 4 , co jeśli spojrzysz na graf, rzeczywiście odpowiada najkrótszej ścieżce od wierzchołka 0 do wierzchołka 4 .

Zamyślony czytelnik mógłby zapytać:

To bardzo dobre pytanie. Jesteśmy pewni, ponieważ aktualizujemy macierz R nową wartością, gdy aktualizujemy wartość najkrótszej ścieżki w macierzy W Tak więc ostatecznie każdy wiersz macierzy R zawiera dane związane z najkrótszymi ścieżkami. Nic więcej, nic mniej.

Teraz, gdy skończyliśmy teorię, czas na wdrożenie.

Implementacja w C#

W poprzednim poście , oprócz zaimplementowania oryginalnej wersji algorytmu Floyda-Warshalla, zintegrowaliśmy także różne optymalizacje: obsługę grafów rzadkich, paralelizmu i wektoryzacji, a na końcu wszystko to połączyliśmy.

Nie ma powodu, aby powtarzać to wszystko dzisiaj. Chciałbym jednak pokazać, jak zintegrować zapamiętywanie tras z oryginalnymi i wektorowymi (z obsługą grafów rozrzedzonych) wersjami algorytmu.

Integracja z oryginalnym algorytmem

Może trudno w to uwierzyć, ale aby zintegrować zapamiętywanie trasy z oryginalną wersją algorytmu, wystarczy:

1. Rozszerz sygnaturę funkcji, aby uwzględnić macierz R jako oddzielny parametr – int[] routes .

   
   

2. Zapisz k w routes za każdym razem, gdy najkrótsza ścieżka zostanie zmieniona (linie: 2 i 14).

To wszystko. Tylko półtora wiersza kodu:

 public void BaselineWithRoutes( int[] matrix, int[] routes, int sz) { for (var k = 0; k < sz; ++k) { for (var i = 0; i < sz; ++i) { for (var j = 0; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; routes[i * sz + j] = k; } } } } }

Integracja z algorytmem wektorowym

Integracja z wersją wektorową (obsługującą rzadkie grafy) wymaga nieco więcej wysiłku, jednak kroki koncepcyjne są takie same:

1. Rozszerz sygnaturę funkcji, aby uwzględnić macierz R jako oddzielny parametr – int[] routes .

   
   

2. W każdej iteracji zainicjuj nowy wektor wartości k (linia: 6).

   
   

3. Zapisz wektor wartości k do routes za każdym razem, gdy zmieni się najkrótsza ścieżka (wiersze: 31-32).

   
   

4. Zaktualizuj niewektorowaną część algorytmu w taki sam sposób, w jaki zaktualizowaliśmy oryginalny algorytm (linia: 41).

 public void SpartialVectorOptimisationsWithRoutes( int[] matrix, int[] routes, int sz) { for (var k = 0; k < sz; ++k) { var k_vec = new Vector<int>(k); for (var i = 0; i < sz; ++i) { if (matrix[i * sz + k] == Constants.NO_EDGE) { continue; } var ik_vec = new Vector<int>(matrix[i * sz + k]); var j = 0; for (; j < sz - Vector<int>.Count; j += Vector<int>.Count) { var ij_vec = new Vector<int>(matrix, i * sz + j); var ikj_vec = new Vector<int>(matrix, k * sz + j) + ik_vec; var lt_vec = Vector.LessThan(ij_vec, ikj_vec); if (lt_vec == new Vector<int>(-1)) { continue; } var r_vec = Vector.ConditionalSelect(lt_vec, ij_vec, ikj_vec); r_vec.CopyTo(matrix, i * sz + j); var ro_vec = new Vector<int>(routes, i * sz + j); var rk_vec = Vector.ConditionalSelect(lt_vec, ro_vec, k_vec); rk_vec.CopyTo(routes, i * sz + j); } for (; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; routes[i * sz + j] = k; } } } } }

Benchmarking

Zbieranie informacji o trasie wydaje się wystarczająco rozsądne, ponieważ… cóż, czemu nie? Zwłaszcza, gdy tak łatwo jest zintegrować je z istniejącymi algorytmami. Zobaczmy jednak, jak praktyczne jest ich domyślne zintegrowanie.

Oto dwa zestawy testów porównawczych: z i bez (oba wykonują oryginalne i wektorowe wersje algorytmu). Wszystkie testy porównawcze zostały wykonane przez v0.13.1 (.NET 6.0.4 x64) na komputerze wyposażonym w procesor Intel Core i5-6200U CPU 2.30GHz (Skylake) i działającym w systemie Windows 10.

Wszystkie eksperymenty przeprowadzono na predefiniowanym zestawie grafów użytym w poprzednim poście : 300, 600, 1200, 2400 i 4800 wierzchołków.

Poniżej znajdują się wyniki testów porównawczych, w których metody Baseline i BaselineWithRoutes odpowiadają oryginalnej wersji algorytmu, a metody SpartialVectorOptimisations i SpartialVectorOptimisationsWithRoutes odpowiadają wektoryzowanej (z obsługą grafów rzadkich) wersji algorytmu.

Metoda	Rozmiar	Średnia (ms)	Błąd (ms)	Odchylenie standardowe (ms)
Linia bazowa	300	40.233	0,0572	0,0477
Linia bazowa z trasami	300	40.349	0,1284	0,1201
SpartialVectorOptimisations	300	4.472	0,0168	0,0140
Częściowe optymalizacje wektorowe z trasami	300	4.517	0,0218	0,0193
Linia bazowa	600	324.637	5.6161	4.6897
Linia bazowa z trasami	600	321.173	1,4339	1.2711
SpartialVectorOptimisations	600	32.133	0,2151	0,1679
Częściowe optymalizacje wektorowe z trasami	600	34.646	0,1286	0,1073
Linia bazowa	1200	2,656.024	6.9640	5.8153
Linia bazowa z trasami	1200	2,657.883	8.8814	7.4164
SpartialVectorOptimisations	1200	361.435	2,5877	2.2940
Częściowe optymalizacje wektorowe z trasami	1200	381.625	3,6975	3.2777
Linia bazowa	2400	21 059,519	38.2291	33.8891
Linia bazowa z trasami	2400	20 954,852	56.4719	50.0609
SpartialVectorOptimisations	2400	3,029.488	12.1528	11.3677
Częściowe optymalizacje wektorowe z trasami	2400	3,079.006	8.6125	7.1918
Linia bazowa	4800	164,869.803	547.6675	427.5828
Linia bazowa z trasami	4800	184,305.980	210.9535	164.6986
SpartialVectorOptimisations	4800	21,882.379	200.2820	177.5448
Częściowe optymalizacje wektorowe z trasami	4800	21,004.612	79.8752	70.8073

Wyniki testów porównawczych nie są proste do zinterpretowania. Jeśli przyjrzysz się bliżej, znajdziesz kombinację, gdy zbieranie tras faktycznie przyspieszyło działanie algorytmu lub nie miało żadnego znaczącego wpływu.

Wygląda to bardzo myląco (i jeśli tak jest – zdecydowanie radzę posłuchać tego z i , aby lepiej zrozumieć, jakie trudne rzeczy mogą wpływać na pomiary). Moim zdaniem „mylące” zachowanie jest spowodowane przez świetną wydajność pamięci podręcznej procesora (ponieważ wykresy nie są wystarczająco duże, aby nasycić pamięci podręczne). Częściowo teoria ta opiera się na „ pogrubionej ” próbce, gdzie możemy zobaczyć znaczną degradację na największym wykresie. Jednak jej nie zweryfikowałem.

Ogólnie rzecz biorąc, testy pokazują, że jeśli nie mamy do czynienia ze scenariuszami wymagającymi ekstremalnie wysokiej wydajności i ogromnymi wykresami, to nie ma problemu z domyślnym zintegrowaniem zapamiętywania tras z obydwoma algorytmami (należy jednak pamiętać, że spowoduje to podwojenie zużycia pamięci, ponieważ będziemy musieli przydzielić dwie macierze W i R zamiast jednej).

Pozostało jedynie zaimplementowanie algorytmu przebudowy trasy.

Implementacja algorytmu przebudowy trasy

Implementacja algorytmów przebudowy tras w języku C# jest prosta i niemal całkowicie odzwierciedla wcześniej zaprezentowany pseudokod (do reprezentacji tablicy dynamicznej używamy LinkedList<T> ):

 public static IEnumerable<int> RebuildWithLinkedList( int[] routes, int sz, int i, int j) { var x = new LinkedList<int>(); var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { x.AddFirst(z); z = routes[i * sz + z]; } x.AddFirst(i); x.AddLast(j); return x; }

Powyższy algorytm nie jest doskonały i zdecydowanie można go ulepszyć. Najprostszym ulepszeniem, jakie możemy wprowadzić, jest wstępne przydzielenie tablicy o rozmiarze sz i wypełnienie jej w odwrotnej kolejności:

 public static IEnumerable<int> RebuildWithArray( int[] routes, int sz, int i, int j) { var x = new int[sz]; var y = sz - 1; // Fill array from the end x[y--] = j; var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { x[y--] = z; z = routes[i * sz + z]; } x[y] = i; // Create an array segment from 'y' to the end of the array // // This is required because 'sz' (and therefore length of the array x) // equals to the number of vertices in the graph // // So, in cases when route doesn't span through // all vertices - we need return a segment of the array return new ArraySegment<int>(x, y, sz - y); }

Chociaż ta „optymalizacja” zmniejsza liczbę alokacji do jednej, niekoniecznie sprawia, że algorytm jest „szybszy” lub „alokuje mniej pamięci” niż poprzedni. Chodzi o to, że jeśli potrzebujemy trasy uporządkowanej od i do j , zawsze będziemy musieli „odwrócić” dane pobierane z macierzy R i nie ma sposobu, aby tego uniknąć.

Jeśli jednak możemy przedstawić dane w odwrotnej kolejności, możemy wykorzystać LINQ i uniknąć niepotrzebnych alokacji:

 public static IEnumerable<int> RebuildWithReverseYield( int[] routes, int sz, int i, int j) { yield return j; var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { yield return z; z = routes[i * sz + z]; } yield return i; }

Istnieje wiele wariantów tego, jak ten kod może zostać „zmieniony” lub „ulepszony”. Ważne jest, aby pamiętać, że każda „zmiana” ma swoje wady pod względem pamięci lub cykli procesora.

Eksperymentuj swobodnie! Możliwości są niemal nieograniczone!

Wniosek

---

W tym poście zagłębiliśmy się w teorię algorytmu Floyda-Warshalla i rozszerzyliśmy ją o możliwość zapamiętywania najkrótszych ścieżek „tras”. Następnie zaktualizowaliśmy implementacje C# (oryginalne i wektorowe) z poprzedniego posta . Na koniec zaimplementowaliśmy kilka wersji algorytmu, aby przebudować „trasy”.

Wiele powtórzyliśmy, ale jednocześnie mam nadzieję, że znalazłeś coś nowego i interesującego w tym. To nie koniec problemu najkrótszych ścieżek dla wszystkich par. To dopiero początek.

Mam nadzieję, że lektura przypadła Ci do gustu. Do zobaczenia następnym razem!