Zaawansowane algorytmy i struktury danych/Ćwiczenia 6

Zadanie 1

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

$C{\times }_{\min }(D+E)=C{\times }_{\min }D+C{\times }_{min}E,$

oraz

$(D+E){\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 {ℛ}$ istnieje cykl o ujemnej wadze.

Rozwiązanie

Dodaj nowy wierzchołek $s$ i skonstruuj graf $G^{\prime }=(V^{\prime },E^{\prime })$ i funkcję wagową $w^{\prime }$ taką, że:

$V^{\prime }=V\cup \{s\}$,

$E^{\prime }=E\cup \{(s,v):v\in V\}$,

$w^{\prime }(u,v)=\{\begin{array}{ll}w(u,v),& \text{jeżeli}(u,v)\in E\\ 0,& \text{jeżeli}u=s\\ 0,\text{w pozostałych przypadkach}\end{array}$.

Zauważmy, że w grafie $G^{\prime }$ 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 {ℛ}$, 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\text{ 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.