Zaawansowane algorytmy i struktury danych/Ćwiczenia 5

Zadanie 1

Zaproponuj efektywny algorytm obliczania najkrótszych ścieżek z jednego wierzchołka w DAGu o dowolnych wagach krawędzi.

Rozwiązanie

Po pierwsze w DAGu nie ma cykli a więc także nie ma cykli o ujemnej wadze. Zauważmy, że wszystkie ścieżki w DAGu idą zgodnie z porządkiem topologicznym, a więc także te najkrótsze. Odległości DAGu można więc policzyć wykonując relaksację krawędzi w porządku topologicznym.

Zadanie 2

Układ ograniczeń różnicowych zadany jest poprzez zbiór zmiennych $X=\{x_0,\dots ,x_n\}$ oraz zbiór nierówności liniowych $O=\{x_{i_0}-x_{j_0}\le b_0,\dots ,x_{i_m}-x_{j_m}\le b_m\}$, gdzie $i_k,j_k\in X$, $b_k\in {ℛ}$ dla $k=0,\dots ,m$. Rozwiązaniem układu ograniczeń różnicowych jest wartościowanie zmiennych $X$ dla którego spełnione są wszystkie nierówności z $O$. Zaproponuj efektywny algorytm znajdujący rozwiązanie układu ograniczeń liniowych.

Rozwiązanie

Problem ten można rozwiązać poprzez sprowadzenie do problemu najkrótszych ścieżek z jednym źródłem i wykorzystanie algorytmu Bellmana-Forda. Mając dane zbiory $X$ i $O$ konstruujemy na ich podstawie graf $G=(X,E)$ oraz funkcję wagową $w:E\to {ℛ}$ w następujący sposób:

$E=\{(x_i,x_j):x_i-x_j\le b\in O\},$ $w(x_i,x_j)=\min \{b:x_i-x_j\le b\in O\}.$

Łatwo teraz pokazać, że w grafie $G$ nie ma cyklu ujemnej długości jeżeli układ ograniczeń różnicowych ma rozwiązanie, oraz odległości w grafie $G$ zadają rozwiązanie tego układu.

Zadanie 3

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$.