Mateusz Gąsiorek 180514

Termin: Środa 16:10

SPRAWOZDANIE

Grafy - Algorytmy Dijkstry oraz Bellmana-Forda

Zaimplementowałem 2 algorytmy :

1) dijkstry,
2) bellmana-forda,

dla trzech struktur, zależnych od danych wejściowych: macierzy incydencji, listy krawędzi oraz listy sąsiadów.

Na wstępie opiszę po krótce sortowania:

Algorytm Dijkstry służy do wyznaczania najmniejszej odległości od ustalonego wierzchołka s do wszystkich pozostałych w skierowanym grafie, w odróżnieniu jednak od Algorytmu Forda-Bellmana, graf wejściowy nie może zawierać krawędzi o ujemnych wagach.
W algorytmie tym pamiętany jest zbiór Q wierzchołków, dla których nie obliczono jeszcze najkrótszych ścieżek, oraz wektor D[i] odległości od wierzchołka s do i. Początkowo zbiór Q zawiera wszystkie wierzchołki a wektor D jest pierwszym wierszem macierzy wag krawędzi A.

Algorytm Bellmana-Forda rozwiązuje problem najkrótszej ścieżki, tj. pozwala znaleźć ścieżkę o najmniejszej wadze pomiędzy dwoma wierzchołkamiw grafie ważonym. Idea algorytmu opiera się na metodzie relaksacji (dokładniej następuje relaksacja V − 1 razy każdej z krawędzi).

W odróżnieniu od algorytmu Dijkstry, poprawność algorytmu Bellmana-Forda nie opiera się na założeniu, że wagi w grafie są nieujemne (nie może jednak występować cykl o łącznej ujemnej wadze osiągalny ze źródła). Za tę ogólność płaci się jednak wyższą złożonością czasową. Działa on w czasie O(V*E).

W dalszej części pracy będę przeprowadzał sprawdzanie złożoności czasowej 2 algorytmów dla kilku różnych plików wejsciówych macierzy wag, listy krawędzi, listy sąsiadów

Swoje wyniki przedstawię w tabeli oraz na wykresach, na koniec wyciągne wnioski wskazując różnice pomiędzy algorytmami:

Swoje doświadczenia przeprowadzam na systemie 32-bitowym Windows 7 pracującym na Intel® Core™2 Duo T5800 2.00GHz. Obliczenia wykonuję za pomocą programu DEV-C++ oraz bibliotek i funkcji związanych z pomiarem czasu w milisekundach.

Grafy przy stałej liczbie:
a) krawędzi
Liczba wierzchołków		Czas:	Dijkstry		Bellmana-Forda
		macierz wag	lista sąsiadów	lista krawędzi		macierz wag	lista sąsiadów
		50	919	190160		1907		0	31
		100	2044	270297		2749		16	62
		200	4286	217760		3578		94	156
		300	9095	194377		6267		343	203
		400	14400	199860		10119		797	250
		500	22120	197783		15307		1891	297
		600	31541	216905		21171		3735	359
		700	44094	201082		28410		6500	422
		800	58000	204470		36307		9843	485
		900	73836	231846		45845		14266	547
		1000	96135	209910		55981		19797	609

Grafy przy stałej liczbie:
b) wierzchołków		Czas:	Dijkstry		Bellmana-Forda
Liczba krawędzi		macierz wag	lista sąsiadów	lista krawędzi		macierz wag	lista sąsiadów
	150	954	2456	1339			16	16
	600	2195	81836	2180			15	47
	1050	2675	191939	2280			15	63
	1500	1807	303518	2771			15	94
	1950	2044	527269	3771			15	125
	2400	2657	778085	4558			16	156
	2850	2435	1126277	5510			16	171
	3300	2616	1493050	7546			15	171
	3750	2850	2028206	7951			16	187
	4200	3212	2377829	8517			16	219
	4650	4086	2933287	8846			16	218

WNIOSKI:

• Przy stałej liczbie krawędzi, algorytm Bellmana-Forda okazuje się szybszy dla listy sąsiadów.

• Przy stałej liczbie wierzchołków, algorytm Bellmana-Forda okazje się szybszy dla macierzy wag.

• Operacje wykonywane na liscie sąsiadów dla algorytmu Dijkstry są dużo wolniejsze niż na pozostałych strukturach.

• Przy stałej liczbie wierzchołków szybszy okazał się algorytm Dijkstry pracujący na macierzy wag

• Przy stałej liczbie krawedzi szybszy okazał się algorytm Dijkstry pracujący na liście krawędzi

---