Student: A
ukasz Rychter Warszawa, 18.01.2010
Nr indeksu: 218882
Grupa studencka: 3M2
Data lab. 8.01.2010 14.15-16.15
Prowadzący: dr inż. Dominik Kasprowicz
Laboratorium AISDE
Sprawozdanie z dwiczenia 5:
Algorytmy grafowe
1) Zadanie i cel dwiczenia
Ćwiczenie ma na celu zapoznanie studenta z przykładowymi implementacjami algorytmów grafowych. Analizowane będą dwa rodzaje algorytmów  znajdujące najkrótszą
drogę w grafie skierowanym (algorytm BruteForce, Floyda i różne implementacje algorytmu Dijkstry) oraz tworzące najmniejsze drzewo rozpinające (MST) w grafie
nieskierowanym (algorytmy Kruskala, Prima i Boruvki).
Algorytmy badamy pod względem złożoności obliczeniowej/pamięciowej i ich przydatności/ograniczeo w różnych zastosowaniach.
2) Warunki przeprowadzenia badań
Dostarczony program został skompilowany w środowisku Microsoft Visual Studio 2005 i uruchomiony na domowym komputerze z systemem Windows. W celu uzyskania
lepszej dokładności pomiaru czasu czasomierz systemowy milisekundowy zastąpiono użyciem funkcji QueryPerformanceCounter() dostosowanej do pomiaru czasu w
mikrosekundach. Dodatkowo dla zminimalizowania wpływu zakłóceo przez procesy pasożytnicze ustawiono maksymalny priorytet procesu za pomocą funkcji
SetPriorityClass( GetCurrentProcess(), REALTIME_PRIORITY_CLASS );
3) Wykonanie poleceń
Do moich zadao należało wykonanie zadao 1,3,7 i 5 lub 9. Wykonałem zarówno zadanie 5, ponieważ było przydatne do wykonania zadania 1, jak i
zadanie 9, ponieważ proste rozwiązanie znalazłem już w czasie laboratorium. Dodatkowo wykonałem zadanie 6, ponieważ było bardzo prostym
uzupełnieniem przy wykonywaniu zadania 5.
Zad 1)  Dla digrafu o kilku wierzchołkach i kilku-kilkunastu krawędziach obserwujemy efekty działania każdego z algorytmów poszukujących najkrótszej drogi między
wszystkimi parami wierzchołków. Jeżeli różne algorytmy dostarczają różnych wyników, należy spróbowad wyjaśnid przyczynę. Graf, wraz z numerami
wierzchołków i wagami krawędzi należy narysowad w sprawozdaniu i zaznaczyd na nim kilka spośród dróg znalezionych przez algorytmy.
Do badao wybrałem graf o 5 wierzchołkach i 12 krawędziach, losowo wygenerowany przy pomocy programu digraphgen. Liczbę wierzchołków i krawędzi
dobrałem tak, aby była ona wystarczająca do zaprezentowania działania algorytmów i zarazem nie skomplikowała nadto schematu.
Rozważany graf:
0
8
1 2
53
3 4
54
83
21
89
4
58
96
39
75
93
Wyniki poszukiwania wszystkich dróg w grafie.
Element w wierszu i i kolumnie j tej macierzy odpowiada długości drogi prowadzącej od wierzchołka i do j.
Algorytmy Dijkstry
0 79 83 58 4
74 0 53 93 39
21 8 0 79 25
58 137 141 0 62
112 75 93 54 0
Algorytm Floyda
104 79 83 58 4
74 61 53 93 39
21 8 61 79 25
58 137 141 116 62
112 75 93 54 114
Algorytm BruteForce
-1 79 83 58 4
74 -1 53 93 39
21 8 -1 79 25
58 137 141 -1 62
112 75 93 54 -1
Wyniki dla algorytmów różnią się tylko na przekątnej macierzy, czyli gdy szukamy drogi mającej początek i koniec w tym samym wierzchołku. Wówczas
wszystkie implementacje algorytmu Dijkstry podają wartośd drogi 0, algorytm BruteForce -1 (oznaczające nieskooczonośd/brak drogi), natomiast algorytm
Floyda wylicza długości najkrótszego cyklu wychodzącego z danego wierzchołka, przechodzącego przez inne i wracającego do początkowego.
Wszystkie te wyniki są zasadniczo poprawne i zależą od interpretacji i przyjętych definicji. Algorytm Floyda pod tym względem prezentuje dodatkową
funkcjonalnośd, jednak nie zawsze pożądaną.
Przykładowe znalezione drogi w grafie:
V0->V3: V0  [4]> V4  [54]> V3 V2->V4: V2  [21]> V0  [4]> V4
łączny koszt 58 łączny koszt 25
0
0
8
8
1 2
1 2
53
53
3 4
3 4
54
54
83
83
21
21
89
89
4
4
58
58
96
96
39
39
75
93
75
93
V3->V1: V3  [58]> V0  [4]> V4  [75]> V1 V3->V3 (tylko dla Floyda): V3  [58]> V0  [4]> V4  [54]> V3
łączny koszt 137 łączny koszt 116
0
0
8
8
1 2
1 2
53
53
3 4
3 4
54
54
83
83
21
21
89
89
4
4
58
58
96
96
39
39
75
93
75
93
Czas w us 19900 krawędzi
V Boruvka Kruskal
Zad 3)  Dla wskazanych przez prowadzącego algorytmów poszukujących najkrótszych dróg w grafie skierowanym i/lub wyznaczających
200 457 1853
najmniejsze drzewo rozpinające grafu nieskierowanego (Kruska, Boruvka) badamy zależnośd czasu obliczeo od liczby wierzchołków V
300 512 1886
przy ustalonej liczbie krawędzi E i vice versa (& )
400 508 1845
500 517 1870
Korzystam z zależności wiążącej liczbę krawędzi w grafie z liczbą wierzchołków: 5V d" E d" V(V-1)/2 600 526 1887
700 523 1890
800 541 1910
Zależnośd czasu obliczeo od liczby wierzchołków przy ustalonej liczbie krawędzi przeprowadzę dla liczby krawędzi 19900. Jest to
900 555 1886
liczba krawędzi dla grafu pełnego o 200 wierzchołkach, będzie to więc dolna granica pomiaru dla wierzchołków; górna granica to
1100 536 1872
19900/5 = 3980, w przybliżeniu 4000 wierzchołków, jako iż granica ta nie jest ścisła. Zakres 200-4000 powinien byd wystarczająco
1200 673 1917
szeroki do badao i zarazem pozwala on uzyskiwad odpowiednio długie czasy obliczeo (co wpływa na zmniejszenie niechcianych
1300 735 1896
fluktuacji wyników). 1400 730 1908
1500 710 1905
1600 730 1911
2500
1700 727 1912
1800 780 1928
1900 793 2086
2000 809 1926
2000
2100 809 2107
2200 826 1941
2300 821 1935
2400 843 1943
2500 867 1907
1500
2600 880 1967
Boruvka
2700 888 1907
2800 897 1952
Kruskal
2900 908 1929
1000
1.6x + 450
3000 926 1956
0.04x + 1850
3100 926 1940
3200 1097 1971
3300 927 2052
500
3400 976 1975
3500 995 2072
3600 999 1978
3700 978 2084
0 3800 1029 1995
3900 1040 2089
0 500 1000 1500 2000 2500 3000 3500 4000
4000 1050 2001
Wierzchołki
Czas w mikrosekundach
Zależnośd czasu obliczeo od liczby krawędzi przy ustalonej liczbie wierzchołków przeprowadzę dla liczby wierzchołków 3000. Daje to wystarczająco duże czasy
działania dla minimalnej liczby krawędzi równej 5V jak i nie przesadnie długie czasy dla grafu pełnego o liczbie krawędzi V(V-1)/2.
W praktyce dla liczby krawędzi równej 5V=15000 graf okazał się zbyt rzadki przez co niespójny, pomiar zacząłem więc od 30000 krawędzi.
Czas w us 3000 wierzchołków
Krawędzie Boruvka Kruskal
1000000
30000 1204 2931
60000 2020 6105
100000 3129 9814
150000 4817 15055
Boruvka
200000 6038 22457
100000
250000 8533 31399
Kruskal
300000 7856 42356
500000 13710 90898
0.1 * x^0.9
750000 19893 161498
1000000 27753 235526
10000
0.007 * x^1.25
1500000 40626 373840
2000000 53507 538674
3000000 58181 893230
4000000 81871 1301405
4498500 78459 1451475
1000
30000 300000 3000000
Krawędzie
Dla obu algorytmów zależnośd czasu wykonywania od liczby wierzchołków przy ustalonej liczbie krawędzi jest w przybliżeniu liniowa (złożonośd O(V)). Dla
Algorytmu Kruskala zależnośd ta jest nieznaczna, liczba wierzchołków w bardzo niewielkim stopniu wpływa na czas obliczeo. Algorytm Boruvki posiada wyższy
współczynnik kierunkowy wzrostu czasu, jednak decydującym czynnikiem jest tu stała wartośd początkowego czasu sortowania krawędzi w algorytmie
Kruskala, przez co algorytm Boruvki jest w całym zakresie szybszy.
Lepsza wydajnośd algorytmu Boruvki uwidacznia się jeszcze bardziej w zależności od liczby krawędzi. Jak widad na wykresie alg. Boruvki posiada złożonośd o
niższym stopniu potęgi.
Teoretyczna złożonośd obu algorytmów, Kruskala i Boruvki to O(E * log(V)). Badane implementacje algorytmów wykazują złożonośd O(E0.9 * V) dla Boruvki i
O(E1.25 * V) dla Kruskala (Z dobrym przybliżeniem O(E1.25)). Rozbieżności od wartości teoretycznej wynikają z samych szczegółów implementacyjnych. W
algorytmie Kruskala dominującym czynnikiem jest złożonośd algorytmu sortowania QuickSort. W algorytmie Boruvki decyduje złożonośd operacji na
strukturze Forest. Zależnośd liniowa, a nie logarytmiczna od ilości wierzchołków może wynikad ze sposobu (nieoptymalnego) implementacji Lasu.
Dodatkowo rozbieżności te nie są znaczne (poprzez różne przekształcenia można by doprowadzid wyznaczoną złożonośd do postaci bliskiej teoretycznej).
Czas w mikrosekundach
Zad 5)  Modyfikujemy dowolną z funkcji programu minpath (Dijkstra, Floyd itp.) tak, by wypisywała na ekran znalezioną najkrótszą drogę, tj. sekwencję wierzchołków
od początkowego do koocowego.
+przy okazji
Zad 6)  Uzupełniamy kod programu minpath tak, by algorytm Brute Force, wywołany w trybie  każdy do każdego wypisywał macierz długości najkrótszych ścieżek,
podobnie jak to robią pozostałe algorytmy.
// Znajduje najkrotsza droge od 'source' do 'destination' metoda pelnego przegladu przestrzeni rozwiazan.
long BruteForce(Digraph *graph, int V, bool *visited,
int current, int dest, long currentCost, long &minCost, int* FinalPath, int* ActualPath) {
long edgeCost, newCost = 0;
visited[current] = true;
static int TmpPathLenght = 0;
ActualPath[TmpPathLenght] = current; //podąża za rekurencją i dodaje do aktualnie badanej ścieżki nowy wierzchołek
TmpPathLenght++;
for (int w = 0; w < V; w++) {
edgeCost = graph->getWeight(current, w);
newCost = currentCost + edgeCost;
if (w != current && edgeCost != INF && visited[w] == false) {
if (w != dest)
BruteForce(graph, V, visited, w, dest, newCost, minCost, FinalPath, ActualPath);
else {
if (Compare(newCost, minCost) < 0)
{
ActualPath[TmpPathLenght] = w; //dodaje ostatni wierzchołek
//Będac w tym miejscu zawsze poprawiamy dotychczasowy wynik. Aktualna ścieżka kandyduje na najlepszą,
//więc kopiujemy ją do ostatecznej
//Po zakończeniu wszystkich obliczeń w FinalPath pozostaje ostatnia, najlepsza ścieżka
memcpy(FinalPath, ActualPath, (TmpPathLenght+1)*sizeof(int));
FinalPath[TmpPathLenght+1] = -1;
minCost = newCost;
}
}
}
}
//wychodzimy z funkcji rekurencyjnej, a więc też wycofujemy się z wierzchołka (usuwamy go z aktualnej ścieżki)
ActualPath[TmpPathLenght] = -1;
TmpPathLenght--;
visited[current] = false;
return minCost;
}
long RunBruteForce(AbstractGraph *graph, int source, int destination, bool findAllPaths) {
long minCost = INF; // Koszt najkrotszej drogi od 'source' do 'destination'.
bool *visited; // 'true', jesli wierzcholek o odpowiednim indeksie zostal juz odwiedzony.
int V = graph->getNumVertices();
int* FinalPath = new int[V+1]; //ostateczna, wynikowa ścieżka
int* ActualPath = new int[V+1]; //ścieżka biężąco rozważana
//zerowanie ścieżki bieżącej (wierzchołki numerowane od 0 wzwyż, więc -1 oznacza wartość specjalną, koniec ścieżki)
memset(ActualPath, -1, (V+1)*sizeof(int));
int result;
visited = new bool[V];
for (int i = 0; i < V; visited[i++] = false);
if (findAllPaths == false)
{
result = BruteForce((Digraph*)graph, V, visited, source, destination, 0, minCost, FinalPath, ActualPath);
//wypisywanie ścieżki
cout << "\n Najkrotsza sciezka: ";
for ( int i=0; FinalPath[i] != -1; ++i )
{
//wypisywanie -[WAGA]>
if (i!=0) cout << " -[" << graph->getWeight(FinalPath[i-1], FinalPath[i]) << "]> ";
cout << 'V' << FinalPath[i]; //wypisywanie wierzchołka np V0
}
cout << "\n\n";
delete[] visited;
delete[] FinalPath;
delete[] ActualPath;
return result;
}
else {
for (int v = 0; v < V; v++) {
for (int w = 0; w < V; w++) {
// Czyscimy pomocnicze struktury danych
minCost = INF;
for (int i = 0; i < V; visited[i++] = false);
cout << '\t' << (result=BruteForce((Digraph*)graph, V, visited, v, w, 0, minCost,
FinalPath, ActualPath));
//dla czytelności wydruku w trybie "każdy do każdego" ścieżki nie są wypisywane
}
cout << '\n';
}
}
delete[] visited;
delete[] FinalPath;
delete[] ActualPath;
return result;
}
Przykładowe wydruki z działania:
Algorytm Brute Force porownujacy wszystkie mozliwe drogi
Algorytm Brute Force porownujacy wszystkie mozliwe drogi
-1 79 83 58 4
Najkrotsza sciezka: V3 -[58]> V0 -[4]> V4 -[75]> V1
74 -1 53 93 39
21 8 -1 79 25
Najkrotsza droga od 3 do 1 ma koszt 137
58 137 141 -1 62
112 75 93 54 -1
Działanie polega na tym, że wewnątrz funkcji BruteForce w dodatkowej tablicy zapisujemy indeksy wierzchołków z aktualnie rozważanej ścieżki. Jeśli spełniony jest
warunek, że uzyskaliśmy nowe rozwiązanie, lepsze od najlepszego dotychczas kopiujemy aktualną ścieżkę na miejsce ścieżki wynikowej. Ostatnia umieszczona w wyniku
ścieżka jest optymalną.
Dokładniejsze opisy działania zawarte w komentarzach wewnątrz kodu.
Zad 7)  Dlaczego algorytmy wyznaczające najmniejsze drzewo rozpinające nie korzystają z reprezentacji krawędzi jako obiektu HalfEdge ?
Obiekt HalfEdge jest reprezentacją krawędzi grafu skierowanego, posiadającą informację o indeksie wierzchołka koocowego. Algorytmy wyznaczające najmniejsze
drzewo rozpinające operują na grafach nieskierowanych i posiadają reprezentację gałęzi jako obiekt Edge, który zawiera informacje o indeksach obu wierzchołków,
które dana krawędz
łączy, nie wyróżniając żadnego z nich.
Stosowanie dla grafów nieskierowanych obiektu HalfEdge wymagałoby 2 takich obiektów dla opisania 1 krawędzi, co jest niepraktyczne i znacznie skomplikowałoby
użycie tej struktury w algorytmach.
Zad 9)  Jak można zmodyfikowad funkcję Kruskal(), by przyspieszyd jej działanie? Reszta uwag jak w poprzednim punkcie.
// Algorytm Kruskala znajdujacy najmniejsze drzewo rozpinajace
Edge** Kruskal(Graph* g) {
Edge** edges = g->getEdges();
long V = g->getNumVertices();
long E = g->getNumEdges();
int mstSize = 0;
// Zwracana tablica krawedzi tworzacych drzewo rozpinajace
Edge** mst = new Edge*[V-1];
Forest *forest = new Forest(V);
qsort(edges, E, sizeof(Edge*), Edge::compareEdgeWeigths);
for (int i = 0; i < E; i++) {
// Jesli kolejna krawedz nie tworzy cyklu z zadnym ze stworzonych dotychczas drzew...
if (forest->addEdge(edges[i]) == true)
// ...to dodaj ja do drzewa rozpinajacego.
mst[mstSize++] = edges[i];
if (mstSize==V-1) break;
}
delete forest;
return mst;
}
Dodano jedynie jedną wyróżnioną linię. Powoduje ona przerwanie obliczeo w przypadku gdy długośd ścieżki jest już równa docelowej (liczbie wierzchołków
minus jeden). W tym momencie mamy już minimalne drzewo rozpinające, połączone są wszystkie wierzchołki, a dodanie kolejnej krawędzi zawsze spowoduje
utworzenie cyklu. Dalsze obliczenia są więc już bezcelowe.
Przykładowy orientacyjny zysk wydajności(dla grafu pełnego o 10000 wierzchołkach):
-w wersji pierwotnej: 20,5s
-w wersji poprawionej: 17,5s
Dla grafu o ustalonej liczbie wierzchołków zysk wydajności maleje wraz z liczba krawędzi (największy zysk dla grafu pełnego).
Zysk jest względnie niewielki, ponieważ głównym czynnikiem decydującym o wydajności jest złożonośd sortowania (w tym wypadku algorytm QuickSort, na
który nie wpływamy)
Ponieważ do moich zadao należało wykonanie zadania 5 LUB 9, a wykonałem zadanie 5, zad 9 wykonuje w skrócie (pomijam szacowanie złożoności
obliczeniowej poprawionej wersji i przytoczenie dokładnego testowania (jednak algorytm został sprawdzony pod względem poprawności działania)).