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.

Najkrótsze ś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 v_i–v_{i+1}należy do E, dla i = 1, 2, ...,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. G=(V,E) – spójny graf nieskierowany; oznaczamy |V| przez n i |E| przez m; n-1 <= m <= n(n-1)/2 w: E―>{1,2,...} – funkcja przypisująca krawędziom dodatnie liczby całkowite; w(e) – waga krawędzi e

Ciąg krawędzi p=<v_0, v_1, ..., v_k> nazywamy ścieżką w G wtedy i tylko wtedy, gdy v_i–v_{i+1}należy do E, dla i = 1, 2, ...,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.