Algorytmy i struktury danych/Algorytmy grafowe - najlżejsze ścieżki

Ten wykład poświęcimy wprowadzeniu do algorytmów grafowych. W tym celu rozwiążemy jedno następujący problem ścieżkowy.

Najlżejsze ścieżki z jednym źródłem

W tym wykładzie pisząc graf będziemy mieli zawsze na uwadze graf spójny i nieskierowany. Tradycyjnie przez $n$ będziemy oznaczali liczbę wierzchołków w grafie, a przez $m$ liczbę jego krawędzi. Dla każdego grafu mamy zawsze $n-1\le m\le n(n-1)/2$.

Niech $G=(V,E)$ będzie grafem, a $w:E\to \{1,2,...\}$ funkcją przypisująca krawędziom dodatnie liczby całkowite zwane wagami krawędzi.

Ciąg wierzchołków $p=<v_0,v_1,\dots ,v_k>$ nazywamy ścieżką w G wtedy i tylko wtedy, gdy Parser nie mógł rozpoznać (błąd składni): {\displaystyle v_i–v_{i+1}} jest krawędzią w $E$, dla każdego $i=1,2,\dots ,k-1$. Liczbę $k$ nazywamy długością ścieżki $p$.

Wagą ścieżki $p$ nazywamy sumę wag jej krawędzi i oznaczamy także przez $w(p)$. Przyjmujemy, że waga ścieżki o długości 0 wynosi 0.

Problem najkrótszych ścieżek z jednym źródłem definiuje się nastepująco.

Dane:
  $G=(V,E)$ – spójny, nieskierowany graf
  $w:E\to \{1,2,\dots \}$ – funkcja przypisująca krawędziom   dodatnie liczby całkowite
  $s$ – wyróżniony wierzchołek w G, zwany źródłem
Wynik:
  dla każdego wierzchołka $v$ waga $w*(v)$ najlżejszej ścieżki łączącej v z s.