46 (452)

53. Podać i omówić algorytm Prima i Dijkstry znajdowania minimalnego drzem rozpinającego. Jaka jest jego złożoność?'

Oio algoryun: var

neir: array (1 . . n] of l..n ; (dii każdego wierzchołka „v", który nie znalazł 5ie

jeszcze w drzewie .w tablicy nezr[v} zapazŁiętu^ e sie najbliższy mu wierzchołek drzewa}

di si: array(l..nj of l..n;    (-z ćpanie tu j e odległość „V" oć najbliższego mu

wierzchołka w drzewie]

b«eęin

(wybierz arbitralnie v-} ; for v£V do

di 5 Z ( v) : - W (v, v - ] ;    [ kos z C krawędzi {v, v_Q) }

near f-v) :»v₀; enc for;

V. := (v_d) ; {wierzchołki drzewa}

Z.. i — 0;    { kraweczie erze w a}

a.:-0;    (sumaryczny koszt drzewa]

whiłe V. <>V do

.ist [ v

v: “wierzchołek z (V - V.) o najnniejsze j wartości

: *V. Ujv};
£::=£; w { {v.	nedr(v))};
W.: =K. 4 dist	(vj ;
for xe{V-V.)	do
if c:s:	( X ) > • ■* i V , X J
d	i sW ( x j : =w { V
near(x):=v;

end z z; end for; end whiłe; tnd {program};

Cóż mogę powiedzieć. Bardziej popiec... algorytmów nie widziałem.. Niezłe z Primy i Dijkstry' były barszczyki! Analiza tej cm pozy kosztowała mnie prawie godzinę. Proponuję jednak każdemu samodzielnie przeanalizować ten algorytm, gdyż me stery nie jestem w stanie wytłumaczyć porządnie jak to działa. Gwarantuję, ze jeśli ktoś rozpisze sobie graf, zapisze na kance tablice r.ear i dist oraz zbiory \\. E, oraz będzie zapisywał w tablicach zmieniające się wartości to po kilku obrotach pętli whiie będzi: wiedział o co chodzi. Aha (!), proszę się nie martwic, że jakoby głupoty się wpisują czasem do tablic. To wszystko się wyjaśnia przy kolejnych obrotach pętli. Dijkstra był chyba po niezłym Sylwestrze kiedy na to 'wpadał. Podaję do porównania moje minimalne drzewo rozpinające dla poniższego grafu. Ważne jes; aby do tablic jeśli nie ma krawędzi między wierzchołkami wpisywać x.

>ablica kosztów krawędzi srafu:    _ •____

Kra węd	u	1,3 1,5	1,7 j 2,3	2,4	3,4	3,6	4,5	5,6
zie		|	1 -

7.8 I 7.9

8.9 ; id~

Powstałe wg. srafu drzewo rozpinające: (kolejno powstawały' krawędzie) (2, 3), (2, 4), (4, 5), (6,5), (l, 2),

(7. l),(8,7),(8,9).

Banachowski, Diks i RyTter piszą sobie, że realizacja tego algorytmu w czasie 0(nj nie powinna wam przysporzyć klopom. Ciekawe, co ???

koszt 10    12

21

17 i S i 8

6 I 7