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