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 }\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.