Zaawansowane algorytmy i struktury danych/Ćwiczenia 6

From Studia Informatyczne

Zadanie 1

Pokaż, że iloczyn odległości jest przemienny względem dodawania, tzn. że dla macierzy C, D i E rozmiaru n\times nzachodzi:


C \times_{\min} \left(D  + E \right)= C \times_{\min} D +   C  \times_{min} E,


oraz


\left(D  + E \right) \times_{\min} C = D \times_{\min} C +   E  \times_{min} C.

Wskazówka

Te dwie równości wynikają ponownie z definicji iloczynu odległości - wzoru (1) oraz przemienności operacji \min względem dodawania.

Zadanie 2


Zaproponuj, jak wykorzystać algorytm Bellmana-Forda do sprawdzenia, czy w grafie G=(V,E) i wagach krawędzi opisanych funkcją w:E \to \mathcal{R} istnieje cykl o ujemnej wadze.

Rozwiązanie

Dodaj nowy wierzchołek s i skonstruuj graf G'=(V',E') oraz funkcję wagową w' taką, że:

V' = V \cup \{s\},

E' = E \cup \{(s,v): v \in V\},

w'(u,v) = \begin{cases}w(u,v), & \mbox{jeżeli} (u,v)\in E\\ 0, & \mbox{jeżeli} u=s\\0, \mbox{w pozostałych przypadkach}\end{cases}.

Zauważmy, że w grafie G' są te same cykle co w grafie G. Jednak teraz wszystkie te cykle są osiągalne z wierzchołka s. Możemy więc do wykrycia cykli o ujemnej wadze użyć algorytmu Bellmana-Forda uruchomionego dla wierzchołka s.


Zadanie 3

Mając dane graf G=(V,E), funkcję wagową w:E \to \mathcal{R}, odległości d(v) z wybranego wierzchołka s do v w grafie G, zaproponuj algorytm obliczania drzewa najkrótszych ścieżek w czasie O(|E|).


Wskazówka

W celu otrzymania drzewa najkrótszych ścieżek z grafu G usuniemy krawędzie, które na pewno nie należą do żadnej najkrótszej ścieżki. Zdefiniujmy graf G_{d} = (V,E_{d}) jako:


E_{d} = \{(u,v): (u,v)\in E \mbox{ i } d(u) + w(u,v) = d(v). \}


Zauważmy, że wszystkie ścieżki w G_{d} są najkrótszymi ścieżkami, a więc dowolne drzewo przeszukiwania grafu G_{d} ukorzenione w s jest drzewem najkrótszych ścieżek.