Skierowane grafy acykliczne (DAG, ang. Directed Acyclic Graphs)
Definicja: Dowolny graf skierowany G taki, że nie posiada cyklu nazywamy grafem skierowanym acyklicznym lub krócej - grafem acyklicznym.
Grafy acykliczne stosowane są głównie do opisu problemów częściowego uporządkowania, np. zbiorów.
Definicja: Operacja częściowego uporządkowania R zbioru S jest relacją binarną taką, że zachodzi:
dla każdego a∈S relacja aRa jest fałszem (własność przeciwzwrotności)
dla każdego a,b,c∈S, jeśli zachodzą relacje aRb oraz bRc, to relacja aRc jest także prawdą (własność przechodniości).
Aby przedstawić relację częściowego uporządkowania przy pomocy DAG należy:
każdy element należący do zbioru S przedstawić jako jeden wierzchołek grafu
dla każdej pary wierzchołków (a,b) poprowadzić krawędź skierowaną od a do b wtedy i tylko wtedy, gdy aRb.
Przykład: Niektóre podręczniki zawierają sugestie w jakiej kolejności należy czytać i studiować zawarty w niej materiał. Sugestie te zawierają operacje częściowego uporządkowania wynikające z faktu, iż zwykle nie można studiować np. rozdziału 2, jeśli nie przestudiowało się rozdziału 1. Zdefiniowanie częściowego uporządkowania (oznaczać będziemy je dalej znakiem ) na zbiorze C rozdziałów i podrozdziałów podręcznika oznacza więc, że dla dowolnej pary rozdziałów a,b∈C podręcznika relacja ab zachodzi wtedy i tylko wtedy, gdy rozdział a poprzedza rozdział b.
Rys. DAG kolejności studiowania pewnego podręcznika
Definicja: Wierzchołek i poprzedza (jest poprzednikiem) wierzchołek j wtedy i tylko wtedy, gdy istnieje droga z i do j.
Definicja: Wierzchołek i bezpośrednio poprzedza (jest bezpośrednim poprzednikiem) wierzchołek j wtedy i tylko wtedy, gdy istnieje w grafie istnieje krawędź (i, j).
Podobne definicje można sformułować dla następnika oraz bezpośredniego następnika.
Uporządkowanie topologiczne
Definicja: Topologiczne uporządkowanie wierzchołków grafu acyklicznego DAG G=(V,E) oznacza takie liniowe uporządkowanie, że jeśli tylko dla dwóch dowolnych wierzchołków i,j∈V wierzchołek i jest poprzednikiem wierzchołka j, to i poprzedza także j w zbiorze liniowo uporządkowanych wierzchołków.
Uporządkowanie topologiczne wierzchołków pozwala nam na takie ich odwiedzanie, że aby żaden wierzchołek nie został odwiedzony, dopóki nie będą odwiedzone wszystkie wierzchołki, z których prowadzi do niego krawędź. Kolejność taka nazywana jest także porządkiem topologicznym, a proces jej znajdowania - sortowaniem topologicznym.
W ogólności, dla danego grafu acyklicznego DAG istnieje więcej niż tylko jeden porządek topologiczny.
Rys.5 Przykłady porządku topologicznego
Przykład: Na rys.5 przedstawiono trzy grafy acykliczne. Pierwszy graf ma tylko jedno uporządkowanie topologiczne, tzn. a b c d. Graf drugi ma dużą liczbę uporządkowań wynoszącą 4! = 24. Z kolei ostatni graf ma więcej niż jeden porządek topologiczny, ale też mniej niż 24 (dwoma przykładami uporządkowania są: a b c d oraz a c b d)
Algorytm porządkowania topologicznego
Poniżej przedstawiono pseudokod algorytmu realizujący uporządkowanie topologiczne grafu acyklicznego G = (V, E). Przyjęto przy tym założenie, że wartość zmiennej numVertex. oznaczająca liczbę wierzchołków grafu (liczność zbioru V), jest z góry znana.
void TopSort (Graph G)
{
unsigned int counter = 1;
Vertex v, w;
Queue <Vertex> q (numVertex);
Array <Vertex> inDegree (numVertex);
for (każdy wierchołek v)
{
inDegree[v] = InDegree(v); // wypełnij elementy wektora inDegree
if (inDegree[v] == 0) // umieść w kolejce wierzchołki
// zerowegostopnia
q.Enqueue(v);
}
while (!q.isEmpty())
{
v = q.Dequeue();
włóż v do zbioru uporządkowanego topologicznie;
counter++;
for (każdy wierzchołek w incydentny z v)
{
inDegree[w] -= 1;
if (inDegree[w] == 0)
q.Enqueue(w);
}
}
if (counter <= numVertex)
Error („Graf zawiera cykl”);
}
Zmienna counter wykorzystywana jest do weryfikacji, czy graf zawiera cykl. Zmienna ta jest inkrementowana zawsze po każdej operacji Dequeue. Jeśli stopień wyjściowy wierzchołka (liczba wychodzących z niego krawędzi) jest zbyt duża (wskutek wystąpienia cyklu), wówczas wartość licznika counter będzie zbyt mała.
Zamiast czekać na zakończenie algorytmu, częściowy test na obecność cyklu w grafie można wykonać natychmiast po zainicjowaniu wektora inDegree. Warunkiem wystarczającym, ale nie koniecznym, obecności cyklu w grafie jest sprawdzenie, czy w grafie nie ma żadnego wierzchołka o zerowym stopniu wyjściowym. Jeśli tak jest, wówczas w grafie może występować cykl.
Przykład: Działanie algorytmu TopSort zilustrujemy na przykładzie grafu DAG z rys.6 .
Rys.6 Przykład grafu dla potrzeb analizy algorytmu TopSort
Początek: Zawartość wektora inDegree
wierzchołek: 1 2 3 4 5 6 7 8 9 10
InDegree: 1 2 2 0 2 1 0 3 2 0
Krok Kolejka v counter
0 --- - 1
1 4,7,10 - 1 // wierzch.o 0 stopniach wejściowych
2 7,10 4 2 // z kolejki 4
wierzchołek: 1 2 3 4 5 6 7 8 9 10 // dopasuj do wierzchołka 4
InDegree: 1 2 1 0 1 1 0 2 1 0
3 10 7 3 // z kolejki 7
wierzchołek: 1 2 3 4 5 6 7 8 9 10 // dopasuj do wierzchołka 7
InDegree: 0 1 0 0 1 1 0 2 1 0
4 1,3 10 4 // z kolejki 10, do kolejki 1 i 3
wierzchołek: 1 2 3 4 5 6 7 8 9 10 // dopasuj do wierzchołka 10
InDegree: 0 1 0 0 0 1 0 2 1 0 // 5 zeruje się
5 3,5 1 5 // z kolejki 1, do kolejki 5
wierzchołek: 1 2 3 4 5 6 7 8 9 10 // dopasuj do wierzchołka 1
InDegree: 0 0 0 0 0 0 0 2 1 0 // 6 i 2 zerują się
6 5,6,2 3 6 // z kolejki 3, do kolejki 6 i 2
wierzchołek: 1 2 3 4 5 6 7 8 9 10 // dopasuj do wierzchołka 3
InDegree: 0 0 0 0 0 0 0 2 1 0 // bez zmian
7 6,2 5 7 // z kolejki 5
wierzchołek: 1 2 3 4 5 6 7 8 9 10 // dopasuj do wierzchołka 5
InDegree: 0 0 0 0 0 0 0 2 0 0 // 9 zeruje się
8 2,9 6 8 // z kolejki 6, do kolejki 9
wierzchołek: 1 2 3 4 5 6 7 8 9 10 // dopasuj do wierzchołka 6
InDegree: 0 0 0 0 0 0 0 2 0 0 // bez zmian
9 9 2 9 // z kolejki 2
wierzchołek: 1 2 3 4 5 6 7 8 9 10 // dopasuj do wierzchołka 2
InDegree: 0 0 0 0 0 0 0 1 0 0 // bez zmian
10 9 10 10 // z kolejki 9
wierzchołek: 1 2 3 4 5 6 7 8 9 10 // dopasuj do wierzchołka 9
InDegree: 0 0 0 0 0 0 0 0 0 0 // 8 zeruje się
11 8 - 11 // do kolejki 8
12 --- 8 12 // z kolejki 8
Koniec
Drzewa rozpinające (ang. spanning trees)
Definicja: Drzewem rozpinającym spójnego grafu G = (V,E) nazywamy minimalny (o najmiejszej liczbie krawędzi) podgraf G' grafu G taki, że G' jest spójny, V(G') = V(G) (ta sama liczba wierzchołków) oraz E(G') ⊂ E(G) (zbiór krawędzi grafu G' jest podzbiorem krawędzi grafu G).
Mówiąc mniej formalnie, drzewem rozpinającym grafu spójnego G jest drzewo składające się wyłącznie z krawędzi z G oraz zawierający wszystkie wierzchołki z G.
Jeśli graf jest niespójny, wtedy otrzymujemy zbiór drzew rozpinających. Zbiór ten nazywamy lasem rozpinającym.
W ogólności, graf posiada więcej niż jedno drzewo rozpinające.
Przykład: Na rys.7 przedstawiono graf spójny oraz kilka przykładów drzew rozpinających.
Rys.7 Graf i kilka jego drzew rozpinających
Drzewo rozpinające można zbudować w oparciu o algorytmy przechodzenia grafu BFS i DFS. Krawędzie, którymi przechodzą te algorytmy tworzą gałęzie drzewa rozpinającego.
Typowe zastosowanie drzew rozpinających polega na połączeniu określonej liczby procesorów (stacji roboczych) przy pomocy minimalnej liczby połączeń sieciowych (przydzielając każdej krawędzi np. wagę równą 1). Drzewa rozpinające tak zdefiniowanego grafu reprezentują wszystkie realne wybory dla sieci komunikacjyjnej o minimalnej liczbie krawędzi.
Dowolny spójny graf acykliczny jest jednocześnie drzewem swobodnym.
Drzewo rozpinające nazywamy często drzewem swobodnym albo drzewem bez korzenia (nie wyróżnia się w nim wierzchołka głównego, typu korzeń).
Twierdzenie: Każde drzewo swobodne o liczbie wierzchołków n ≥ 1 zawiera dokładnie n-1 krawedzi.
Dowód: (przez indukcję).
Warunek początkowy: Dla n = 1 twierdzenie jest prawdziwe (brak krawędzi).
Założenie indukcyjne: Załóżmy, n = N twierdzenie jest słuszne (tzn. Drzewo swobodne zawiera dokładnie N - 1 krawędzi..
Krok indukcyjny: Dodajmy kolejny wierzchołek do drzewa swobodnego, zawierającego N wierzchołków, łącząc go z drzewem porzez nową krawędź z pewnością nie zamkniemy cyklu. Z założenia indukcyjnego wynika, że oryginalne (wyjściowe) drzewo miało N - 1 krawędzie. Stąd obecnie posiada ich N.
CND
Twierdzenie: Jeśli do drzewa swobodnego dodać krawędź (ale nie wierzchołek), to w tak otrzymanym grafie powstanie cykl.
Dowód: (przez zaprzeczenie).
Załóżmy, że dodanie krawędzi do drzewa swobodnego o n wierzchołkach nie spowoduje powstania cyklu. Wówczas tak otrzymane drzewo jest nadal drzewem swobodnym, posiadającym n wierzchołków i n krawędzi. Taka sytuacja narusza jednak tezę poprzedniego twierdzenia.
CND\
Definicja: Minimalnym drzewem rozpinającym (MST, ang. minimum spanning tree) nazywamy drzewo swobodne grafu ważonego takie, że suma wag przypisanych krawędziom jest minimalna.
Twierdzenie: Każde minimalne drzewo rozpinające spełnia następującą własność:
Niech dla pewnego nieskierowanego i ważonego grafu G = (V,E) U będzie podzbiorem V takim, że ani U ani V-U nie są zbiorami pustymi. Niech (u,v) będzie krawędzią o najmniejszej wadze (koszcie) taką, że u∈U, zaś v∈V-U. Wtedy zawsze istnieje minimalne drzewo rozpinające, zawierające krawędź (u,v).
Uwaga. Przedstawiona własność MST nie oznacza, że każde minimalne drzewo rozpinające zawiera krawędź (u,v). Oznacza jedynie tylko tyle, że krawędź tą zawiera jakieś minimalne drzewo rozpinające.
Rys.8 Ilustracja własności MST
Przykład: Załóżmy, że w przypadku grafu z rys.8 U = (B,C). Wówczas zawsze istnieje minimalne drzewo rozpinające, zawierające krawędż (A,B).
Algorytm Prima wyznaczania MST:
Rozpoczynamy od zbioru pustego: U=. Następnie do zbioru U dodawane są sukcesywnie te wierzchołki ze zbioru V-U, które z wierzchołkami już należącymi do zbioru U tworzą krawędzie o najmniejszych wagach.
włóż do zbioru U dowolny wierzchołek; // U jest początkowo pusty
while (V-U nie jest pusty)
{
znajdż krawędż (u,v) o najmniejszej wadze taką, że u∈U, zaś v∈V-U;
dodaj wierzchołek v do zbioru U (usuwając go jednocześnie z V-U)
}
Algorytm Prima jest klasy O(|V|2), ponieważ potencjalnie każdy z wierzchołków może być dodany do zbioru U i, co więcej, za każdym razem musimy przeglądać wierzchołki pozostałe w V-U.
Przykład: W przypadku grafu przedstawionego na rys.10 algorytm Prima rozpoczynamy z U=a. Sekwencyjnie powtarzając kroki algorytmu otrzymamy, że zbiór U w kolejnych iteracjach będzie miał postać: iteracja 1 - U = {a,c}, iteracja 2 - U = {a,c,f}, iteracja 3 - U = {a,c,f,d}, iteracja 4 - U = {a,c,f,d,b} i iteracja 5 - U = {a,c,f,d,b,e}. Całkowita waga (koszt) minimalnego drzewa rozpinającego wynosi 15.
Rys.10 Ilustracja algorytmu Prima
Algorytm Kruskala
W przeciwieństwie do algorytmu Prima, algorytm Kruskala nie wymaga każdorazowego przeglądania wszystkich wierzchołków (ze zbiorów U i V-U) w celu znalezienia krawędzi o minimalnych wagach. Zamiast tego, bazuje on na zachłannym podejściu do projektowania algorytmów i wybiera za każdym razem odpowiednią krawędź o minimalnej wadze.
Rozpoczynamy od wierzchołków grafu G, bez krawędzi. Daje to nam zbiór |V| spójnych składowych (każdy pojedynczy wierzchołek stanowi osobną spójną składową). Badamy wszystkie krawędzie grafu wyjściowego, zaczynając od tej o najmniejszej wadze, potem biorąc kolejną najlżejszą z pozostałych i tak dalej, dodając za każdym razem analizowana krawędź do drzewa rozpinającego, jeśli tylko nie powoduje to utworzenia cyklu. Liczba krawędzi, potrzebna do utworzenia drzewa rozpinającego wynosi |V|-1.
utwórz listę krawędzi L, uporządkowaną niemalejąco zgodnie z wagami przypisanymi krawędziom;
while (liczba wybranych krawędzi < |V|-1)
{
w = L.Remove(); // pobierz z czoła listy krawędź (ma ona //najmniejszą wagę z spośród pozostałych, //nie wybranych)
if (w łączy dwa spójne składowe)
wybierz krawędź w i dodaj do minimalnego drzewa rozpinającego;
else // krawędź należy już do składowej spójnej
nie wybieraj krawędzi w // mogłoby to przyczynic się do powstania cyklu
}
Analiza algorytmu Kruskala: O(|E| lg|E|) - posortowanie krawędzi; w każdej iteracji: O(lg|E|) - odnalezienie krawędzi o najmniejszej wadze, O(lg|E|) - odnalezienie spójnej składowej, zawierającej analizowaną krawędź, O(lg|E|) - połączenie dwóch składowych spójnych.
Weryfikacja, czy krawędź znajduje się w składowej spójnej jest równoznaczne ze sprawdzeniem członkostwa wierzchołków (formujących tą krawędź) w zbiorze, definiującym składową spójną. Można pokazać, że operacja ta jest klasy O(lg|E|).
Algorytm Kruskala należy do klasy algorytmów zachłannych. Wynika to z faktu, iż zawsze pobiera się w nim (jako następną) krawędź o najniższej wadze.
Algorytm Kruskala działa prawidłowo nawet w przypadku, gdy pewne krawędzie maja przypisane ujemne wagi.
11. Algorytm znajdowania najkrótszej ścieżki
Definicja: Problem znajdowania najkrótszej ścieżki z pojedynczym wyróżnionym wierzchołkiem formułowany jest następująco: Dla danego ważonego grafu G=(V,E) oraz pewnego wyróżnionego wierzchołka s∈V znależć wszystkie ścieżki o minimalnej sumarycznej wadze, prowadzące od wierzchołka s do wszystkich pozostałych węzłów grafu.
W przypadku grafów nieważonych problem znajdowania najkrótszej ścieżki z pojedynczym wierzchołkiem żródłowym jest równoznaczny z rozwiązaniem identycznego zadania dla grafu ważonego, w którym każdej krawędzi przypisano umownie wagę równą 1.
Rys.11 Graf ilustrujący przykłady znajdowania najkrótszej ścieżki
Przykład: W grafie z rys.11 najkrótsza i o minimalnym koszcie ścieżka z wierzchołka 1 do 6 składa się z wierzchołków (1,4,7,6). Całkowita waga tej ścieżki wynosi 6. W przypadku grafu nieważonego, minimalna waga najkrótszej ścieżki także z wierzchołka 1 do 6 wynosi tylko 2, zaś sama ścieżka ma postać (1,4,6) lub (1,3,6). Jak widać, najkrótsza ważona lub nieważona ścieżka nie musi być koniecznie unikalna.
11.1 Najkrótsza nieważona ścieżka o pojedynczym wierzchołku żródłowym
Podstawowa idea algorytmu znajdowania najkrótszej nieważonej ścieżki o pojedynczym wyróżnionym wierzchołku polega na zastosowaniu algorytmu BFS przechodzenia grafu wszerz (począwszy od wierzchołka wyróżnionego - żródłowego) oraz rejestrowaniu odległości (wag) do wierzchołka ku któremu zmierzamy.
Przedstawiony poniżej pseudokod konkretyzuje przedstawioną powyżej ogólną ideę. Przyjęto w nim następujące oznaczenia: T - macierz, zawierająca rekordy opisujące wierzchołki grafu, odległości oraz ścieżki, i zdefiniowana w ten sposób, że T[i].Dist określa odległość wierzchołka i od wierzchołka żródłowego, zaś T[i].Path zawiera wierzchołek, z którego osiągnieto wierzchołek i w trakcie poruszania się najkrótszą ścieżką od wierzchołka żródłowego. Początkowo przyjmuje się, że T[i].Dist = dla każdego i.
void UnweightedShortestPath (Table T)
{
grapphVertex v, w;
Queue<graphVertex>(numVertex) q;
// numVertex - liczba wszystkich wierzchołków grafu
q.Enqueue(S); // kolejka rozpoczyna się od wierzchołka żródłowego
while (!q.IsEmpty())
{
v = q.dequeue();
for (każdy wierzchołek w incydentny do v)
if (T[w].Dist == ) // wierzchołek nie był jeszcze odwiedzony
{
T[w].Dist = T[v].Dist + 1;
T[w].Path = v;
q.Enqueue (w);
}
}
}
Przykład: Jeśli uruchomić algorytm dla przypadku grafu z rys.11 (w wersji nieważonej) o przypisanych krawędzim wagach jednostkowych i wierzchołku żródłowym 3, zawartość macierzy T po zakończeniu algorytmu będzie wyglądała tak jak w poniżej przedstawionej tabeli:
Tab.1 Zawartość macierzy T
Wierzchołek |
Dist |
Path |
1 |
1 |
3 |
2 |
2 |
1 |
3 |
0 |
0 |
4 |
2 |
1 |
5 |
3 |
2 |
6 |
1 |
3 |
7 |
3 |
4 |
Propozycję procedury, która drukuje ścieżkę z danego wierzchołka v (wierzchołek końcowy najkrótszej drogi) do wierzchołka początkowego można przedstawić następująco:
void PrintPath (graphVertex v, Table T)
{
if (T[v].Path != NotAVertex)
{
PrintPath(T[v].Path, T);
cout << „ -> „;
}
cout << V;
}
Przykład: Aby wydrukować drogę (ścieżkę) od wierzchołka 3 do 5 w oparciu o informacje zawarte macierzy T (patrz Tab.1) należy wywołać procedurę PrintPath z parametrami 5 i T. W wyniku otrzymamy następujacą ścieżkę: 3 -> 1 -> 2 -> 5.
11.2 Najkrótsza ważona ścieżka o pojedynczym wierzchołku żródłowym
Do znajdowania najkrótszej ważonej ścieżki o pojedynczym wyróżnionym wierzchołku stosuje się algorytm Dijkstry, należący do klasy algorytmów zachłannych.
Algorytmy zachłanne doskonale nadają się do szukania lokalnie dopuszczalnych rozwiązań.
Algorytm Dijkstry działa dotąd poprawnie dopóki wszystkie wagi przypisane krawędziom mają wartości dodatnie. Każde lokalnie dozwolone rozwiązanie, otrzymane przy tym zastrzeżeniu, jest także dozwolonym rozwiązanie globalnym (pokażemy to póżniej).
Pseudokod algorytmu Dijkstry dla grafu o dodatnich wagach przedstawiono poniżej. G=(V,E) jest grafem. Niech D(v) będzie odległością od wierzchołka żródłowego do wierzchołka v. Przez C(u,v) oznaczmy wagę przypisaną krawędzi (u,v), przez S zbiór wierzchołków (początkowo pusty), zaś przez P(v) wierzchołek, z którego osiągnięto wierzchołek v w trakcie poruszania się najkrótszą ścieżką od wierzchołka żródłowego.
dodaj wierzchołek żródłowy do zbioru S;
// zainiciuj D (sprawność klasy O(|V|)
for (każdy wierzchołek v w zbiorze V-S)
D(v) = C(wierzchołek żródłowy, v);
while (V-S nie jest pusty) // należy to wykonać O(|V|) razy
{
niech w będzie wierzchołkiem ∈ V-S o minimalnej wadze (D(w) -> min);
dodaj w do zbioru S; // usuwając jednocześnie z V-S
for (każdy wierzchołek v ∈ V-S incydentny do w)
if (D[w] + C(w,v) < D[v])
{
D[v] = D[w] + C(w,v);
P[v] = w;
}
}
Twierdzenie 7: Algorytm Dijkstry dla grafu G = (V,E) ważonego o nieujemnych wagach pracuje prawidłowo, dając zawsze dozwolone rozwiązanie globalne.
Rys.12 Algorytm Dijkstry: hipotetyczna najkrótsza ścieżka do wierzchołka w
Dowód: (przez zaprzeczenie). Zgodnie z algorytmem, w każdym kroku znajdujemy najkrótszą ścieżkę incydentną do wierzchołka w∈V-S, całkowicie zawartą w zbiorze S (poza tylko krawędziami, które prowadzą z S do V-S). Nie może więc istnieć inna krótsza ścieżka, prowadząca od wierzchołka żródłowego do wierzchołka w. Jeśli istniałaby wówczas musielibyśmy w pewnym momencie opuścić zbiór S. Rys.12 pokazuje hipotetyczną najkrótszą ścieżkę, prowadzącą z wierzchołka x∈V-S i pozostającą najpierw w V-S i S, by w końcu wrócić do wierzchołka w∈V-S. Jeśli ta ścieżka jest krótsza od ścieżki znalezionej przy pomocy algorytmu Dijkstry, wówczas część ścieżki x jest krótsza od całej ścieżki prowadzącej do w. Ale w takiej sytuacji, D(x) jest krótsza aniżeli D(w) i wierzchołek x powinien był zostać wybrany dużo wcześniej przed wyborem w.
12. Problem znalezienia najkrótszych ścieżek dla wszystkich par wierzchołków
Definicja: Dla danego ważonego grafu skierowanego G=(V,E) problem znalezienia najkrótszych ścieżek dla wszystkich par wierzchołków (APSP, ang. all-pairs shortest problem) polega na wygenerowaniu macierzy (o wymiarze |V|*|V|), której element (i,j) określa najkrótszą ścieżkę pomiędzy wierzchołkiem i a j.
macierznajdowania najkrótszej ścieżki z pojedynczym wyróżnionym wierzchołkiem formułowany jest następująco: Dla danego ważonego grafu G=(V,E) oraz pewnego wyróżnionego wierzchołka s∈V znależć wszystkie ścieżki o minimalnej sumarycznej wadze, prowadzące od wierzchołka s do wszystkich pozostałych węzłów grafu.
Jeden ze sposobów rozwiązania tak sformułowanego problemu polega na |V| krotnym zastosowaniu algorytmu Dijkstry, po jednym razie na dla każdego wierzchołka grafu (zdefiniowany jako wierzchołek żródłowy). Dla grafów rzadkich (o małej liczbie krawędzi, pamiętanych w formie listy) algorytm Dijkstry jest klasy O(|E| lg|V|), stąd APSP klasy O(|V||E| lg|V|). Z kolei w przypadku grafów gęstych (złożonych), opisywanych przy pomocy macierzy incydencji, algorytm Dijkstry jest klasy O(|V|2), zaś APSP klasy O(|V|3).
12.1 Algorytm Floyda rozwiazania problemu APSP
Algorytm Floyda rozwiązujący problem APSP jest klasy O(|V|3), ale wymaga tylko protych operacji macierzowych. Z tego powodu, pomimo że jego asymptotyczna złożoność jest taka sama, jak w przypadku algorytmu Dijkstry dla grafów gęstych (wykonywanego |V| razy), stała proporcjonalności może być dużo mniejsza w przypadku algorytmu Floyda.
W przypadku grafów dostatecznie rzadkich algorytm Dijkstry jest lepszy od algorytmu Floyda.
Algorytm Floyda, oprócz konieczności przechowywania macierzy kosztów (wag krawędzi), wymaga obecności macierzy wag ścieżek (obie macierze są wymiaru |V|*|V|. Niech W(i,j) oraz C(i,j) będą odpowiednio elementem macierzy wag oraz kosztów. Początkowo W(i,j)=C(i,j).
Algorytm Floyda wykonuje |V| iteracji na macierzy W. Po k-tej iteracji, macierz W będzie zawierała najkrótszą (najtańszą) ścieżkę z wierzchołka i do wierzchołka j, nieprzechodzącą przez jakikolwiek wierzchołek o numerze większym niż k.
W k-tym algorytm Floyda wykonuje następująca operację:
Innymi słowy, jeśli w grafie istnieje krótsza ścieżka prowadząca przez wierzchołek k, to dołącz wierzchołek do ścieżki. Sytuację tą ilustruje rys.13.
Rys.13 Algorytm Floyda: Ścieżki prowadzące przez wierzchołki i, j oraz k
Pseudokod algorytmu Floyda ma postać:
// zainiciuj macierz W
for (każdy wierzchołek i)
for (każdy wierzchołek j)
W[i,j] = C[i,j];
for (każdy wierzchołek k)
for (każdy wierzchołek i)
for (każdy wierzchołek j)
W[i,j] = MIN (W[i,j], W[i,k]+W[k,j]);
Ze względu na potrójną pętlę, przeglądającą wszystkie wierzchołki grafu, algorytm Floyda jest klasy O(|V|3).
Spójna składowa jest maksymalnym zbiorem wierzchołków takich, że między każdą parą wierzchołków z tego zbioru istnieje droga
1