« poprzedni punkt   następny punkt »


4. Problem najkrótszych ścieżek

Dany jest graf zorientowany G = <V, E> i funkcja przypisująca krawędziom grafu liczby rzeczywiste, c: E ® R+. Funkcję c nazywamy funkcją kosztu.  Problem, którym będziemy się zajmować w tej części wykładu polega na znalezieniu najkrótszych dróg między wierzchołkami tego grafu.

Definicja 4.1 Niech p oznacza dowolną drogę (ścieżkę) od u do v w grafie G = <V, E>, p = (v0,v1,..., vk) oraz u = v0, v =  vk. Koszt drogi p, d(p), definiujemy jako  sumę kosztów krawędzi, leżących na tej drodze,

d(p) = Si=0,..., k-1 c(vi,vi+1).

Długość najkrótszej ścieżki od u do v oznaczamy przez  d(u,v),  d(u,v) = minpd(p), gdzie minimum rozciąga się na wszystkie drogi p prowadzące od u do v.

Zauważmy najpierw, że najkrótsza ścieżka, o ile istnieje, musi być drogą prostą, tzn. taką, że wszystkie wierzchołki tej drogi są różne. Jest oczywiste, że gdyby na pewnej drodze znajdował się cykl, to usunięcie go zmniejszyłoby koszt drogi. Z drugiej strony, jeśli mamy najkrótszą ścieżkę od u do v, to tym samym mamy najkrótsze ścieżki między dowolnymi dwoma wierzchołkami tej ścieżki. Inaczej mówiąc, podścieżki najkrótszych ścieżek są same najkrótszymi ścieżkami.

 

Twierdzenie 4.1  Niech p = (v0,v1,..., vk) będzie najkrótszą ścieżką od v0 do vk  i niech pij = (vi,vi+1,..., vj) będzie podścieżką p, i<j £k. Wtedy pij jest najkrótszą ścieżką od vi do vj.

Z twierdzenia 4.1 wynika natychmiast, że dla dowolnej pary wierzchołków u, v, jeśli istnieje ścieżka od u do v,oraz v' jest wierzchołkiem poprzedzającym v na tej ścieżce, to

  d(u,v) =  d(u,v') + c(v,v').

Problem najkrótszych ścieżek można rozważać w trzech wariantach:

I. Dla danego grafu zorientowanego znaleźć najkrótszą ścieżkę między dwoma danymi wierzchołkami.
II. Znaleźć najkrótsze ścieżki od wyróżnionego wierzchołka, zwanego źródłem, do wszystkich innych wierzchołków grafu.
III. Znaleźć najkrótsze ścieżki między dowolnymi wierzchołkami grafu.

Chociaż problem pierwszy, wydaje się być najłatwiejszy, to nie jest znane żadne jego rozwiązanie asymptotycznie lepsze niż rozwiązanie polegające na znalezieniu najkrótszych dróg z ustalonego wierzchołka do wszystkich innych (problem II) i wybranie interesującej nas konkretnej ścieżki. Problem trzeci również można rozwiązać wykorzystując rozwiązanie problemu II. Zajmiemy się więc bardziej szczegółowo problemem II.

Zauważmy, że w szczególnym przypadku, gdy koszty wszystkich krawędzi są takie same mamy d(u,v) = c(u,v) * dł, gdzie dł jest długością minimalnej ścieżki od u do v. W tym przypadku problem najkrótszych ścieżek można rozwiązać stosując algorytm BFS przeglądania grafu "wszerz".

Załóżmy, że dany jest graf spójny, którego każdy wierzchołek ma dwa dodatkowe atrybuty m,d. Atrybut m służy do markowanie wierzchołków, a atrybut d, będzie służył do przechowywania odległości od źródła. Przyjmijmy, że graf jest dany w postaci tablicy list sąsiedztwa (incydencji). Algorytm wykorzystuje kolejkę FIFO, początkowo zawierającą tylko wierzchołek- źródło, zamrkowany jako odwiedzony i z atrybutem d=0. Przeglądanie "wszerz" realizuje się, podobnie jak w przypadku drzew:

 

Dopóki kolejka nie jest pusta wykonuj:
1. wyjmij z kolejki pierwszy wierzchołek v i wstaw do niej wszystkie wierzchołki z jego listy sąsiedztwa, o ile nie były jeszcze zamarkowane,
2.dla każdego dopisanego do kolejki wierzchołka u, przyjmij u.d := v.d + 1;
3.zamarkuj wierzchołki wstawione w tym kroku do kolejki.
Czytelnik zechce samodzielnie zapisać szczegóły tego algorytmu.

Na zakończenie tego punktu zauważmy jeszcze, że graf utworzony przez najkrótsze ścieżki ze źródła s, tworzy drzewo o korzeniu w s. Drzewo to nie musi być jedyne.

Przykład 4.1

Na rysunku 11.4 przedstawiono graf i dwa różne drzewa najkrótszych ścieżek ze źródła s. Ze źródła do wierzchołka v prowadzš różne najkrótsze ścieżki: s-u-v w pierwszym drzewie, lub s-u-x-v w drugim.


Pytanie 5:: Jaki jest koszt algorytmu przeglądania grafu o m krawędziach i n wierzchołkach metodą BFS ?



« poprzedni punkt   następny punkt »