[ Pobierz całość w formacie PDF ]

Dodatkowo zamieszczamy obliczenia dla tego samego grafu przy starcie
z wierzchołka 5.
nowy nowa kraw w T
iter wartości dist(v) dla wierzchołków
v w T
u_v waga
1 2 3 4 5 6 7
999 999 999
0 5 14 19 + 24 - -
999
1 3 27 28 + 19 - 24 5_3 14
999
2 4 27 20 - + - 18 5_4 19
3 6 27 20 - - - + 22 4_6 18
4 2 27 + - - - - 22 4_2 20
5 7 27 - - - - - + 6_7 22
6 1 + - + - - - - 3_1 27
near 3 4 5 5 / 4 6 |T| 120
Niżej podano porównanie efektywności algorytmów:
Kruskala i Prima-Dijkstry.
Czasy obliczeń algorytmów MST (msek) (przykłady)
Sieci Liczba Kruskala Prima-
z
ródło:
krawędzi Dijkstry
M.Sysło i inni -
sieci gęste
Algorytmy
790 64 52
o 80 wierz-
optymalizacji
1580 95 51
chołkach
dyskretnej
3160 186 50
PWN
sieci rzadkie
200 44 78
o 100 wierz-
300 66 80
chołkach
Jak widać, algorytm Prima Dijkstry jest równie efektywny dla sieci
gęstych i rzadkich, czas obliczeń zależy praktycznie tylko od liczby
wierzchołków. Natomiast na czas obliczeń algorytm Kruskala istotny
wpływ ma zarówno liczba wierzchołków jak i liczba krawędzi. Przy tym
dla sieci rzadkich algorytm Kruskala może być bardziej efektywny niż
algorytm Prima  Dijkstry.
grafy (czI)
17 [ Pobierz całość w formacie PDF ]