9524140564

1.    Alj»rytm Dijkstry

a| uzupełnić kawałek kodu podany na kartce (trzeba było dopisać warunek <l[v] > d(u| • v»tu. v))

b) tak-t przykładowy implementacje kolejki mami było by użyć w podanym kodzie. I jakie złożoności miały by 3 funkcje użyte w kodzie

c> Złożoność obliczeniowa algorytmu I poszczególnych elementów kodu, za pomoc* N-wierzchołków I M •krawędzi

d) Złożoność obliczeniowa algorytmu za pomocy N.wierzchołków (trzebi było też napisać dlaczego tak się da)

2.    Algeryim Brllmana-Forda

a)    Uzupełnić kawałek kodu (w głównej pętli trzebi było podić Ile razy będzie tlę lierować (N-l))

b)    Dlaczego ma się tyłe razy lierować tj złożoność obliczeniowa algorytmu

d) dopisać ru końcu kod który wykryje czy algorytm wpadł w ujemny cykl

3.    S pytań prawdaiahz

a)    Czy Algorytm Bel Imana-Forda dzlab da ujemnych cykli

b)    Czy Algorytm Dljkstry działa dla ujemnych wag

c)    Czy Belłmana-Fonla dzlab da ujemnych wag

d)    Czy algorytm Prima tworzy las rozpinający

e)    Czy Istnieje tylko Jedno Minimalne drzewo rozpinające w grafie

4.    Algorytm K ni skala

a)    Podany jest graf z wagami I trzeba było wypisać krok po kroku wszystkie Azowa rozplmjęcc jakie powstają

b)    I .|rzru waga lego drzewa po wykonaniu algorytmu

c)    Złożoność algorytmu

d)    Złożoność algorytmu Pnma

5.    Przechodnie domknięcia

a)    Przedstawić przechodnie domknięcie podanego grafu

b)    Jak możni wykorzystać algorytm l-łoyda-Wanbilb do wyznaczenia przechodniego domknięcia