Zaawansowane algorytmy i struktury danych/Wykład 5

Abstrakt

Pierwsza część tego wykładu poświęcona będzie problemowi obliczania najkrótszych ścieżek w grafie z jednego źródła w przypadku, w którym wagi krawędzi mogą być ujemne. Zaprezentujemy algorytm Bellmana-Forda, który rozwiązuje ten problem w czasie $O(|V||E|)$. W drugiej części zajmiemy się problemem obliczania odległości między wszystkimi parami wierzchołków. Pokażemy związki tego problemu z mnożeniem macierzy.

Definicja problemu

W wykładzie tym zajmiemy się problemem obliczania najkrótszych ścieżek w grafie wychodzących z jednego wierzchołka. Załóżmy, że mamy dany graf $G=(V,E)$, funkcję $w:E\to {ℛ}$ przypisującą wagi krawędziom oraz jeden wybrany wierzchołek $s$. Wagę ścieżki $p=(v_0,v_1,\dots ,v_k)$ definiujemy jako wagę tworzących ją krawędzi:

$w(p)=\sum _{i=0}^{k-1}w(v_i,v_{i+1}).$

Odległość z wierzchołka $u$ do wierzchołka $v$ definiujemy jako

$\delta (u,v)=\{\begin{array}{ll}\min \{w(p):p\text{ ścieżka z }u\text{ do }v\},& \text{jeżeli istnieje ścieżka z }u\text{ do }v,\\ \mathrm{\infty }& \text{w przeciwnym przypadku.}\end{array}$

Najkrótszą ścieżką z wierzchołka $u$ do wierzchołka $v$ jest każda ścieżka $p$ z $u$ do $v$, której waga $w(p)$jest równa odległości $\delta (u,v)$ z $u$ do $v$.