Zaawansowane algorytmy i struktury danych/Wykład 5

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 . 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 , funkcję przypisującą wagi krawędziom oraz jeden wybrany wierzchołek . Wagę ścieżki definiujemy jako wagę tworzących ją krawędzi:



Odległość z wierzchołka do wierzchołka definiujemy jako

Najkrótszą ścieżką z wierzchołka do wierzchołka jest każda ścieżka z do , której waga jest równa odległości z do .

W problemie najkrótszych ścieżek z jednego wierzchołka chcemy obliczyć odległości dla wszystkich wierzchołków wraz z drzewem najkrótszych ścieżek z . Drzewem najkrótszych ścieżek o korzeniu w nazywamy podgraf skierowany , w którym , taki, że:

  • jest zbiorem wierzchołków w do których istnieje ścieżka z ,
  • jest drzewem którego korzeniem jest ,
  • dla każdego wierzchołka jedyna ścieżka z do w grafie jest najkrótszą ścieżką z do w grafie .

W naszych algorytmach drzewo najkrótszych ścieżek będziemy reprezentować jako funkcję poprzedników określającą poprzednika wierzchołka w drzewie najkrótszych ścieżek. Drzewo najkrótszych ścieżek możemy uzyskać z w następujący sposób:

Algorytm Bellmana-Forda

Algorytm Bellmana-Forda służy do rozwiązania problemu znalezienia najkrótszych ścieżek w grafie, w którym wagi krawędzi mogą być ujemne. W problemie tym mamy dany graf i funkcję wagową . Algorytm Bellmana-Forda wylicza dla zadanego wierzchołka , czy istnieje w grafie cykl o ujemnej wadze osiągalny z . Jeżeli taki cykl nie istnieje to algorytm oblicza najkrótsze ścieżki z do wszystkich pozostałych wierzchołków wraz z ich wagami.

Relaksacja

Podobnie ja to było w Algorytmie Dijkstry użyjemy metody relaksacji. W metodzie tej utrzymujemy dla każdego wierzchołka wartość będącą górnym ograniczeniem wagi najkrótszej ścieżki z do . W algorytmie utrzymywać będziemy także dla każdego wierzchołka wskaźnik wskazujący na poprzedni wierzchołek przez który prowadzi dotychczas znaleziona najkrótsza ścieżka. Na początku, wielkości te inicjujemy przy pomocy następującej procedury:


Algorytm Inicjacja algorytmu najkrótszych ścieżek


 INICJACJA
 1  for każdy wierzchołek  do
 2  begin
 3    
 4    
 5  end
 6  
 7  return 


Ustalone przez tą procedurę wartości są dobrymi ograniczeniami górnymi na odległości.

Relaksacja krawędzi polega na sprawdzeniu, czy przechodząc krawędzią z do , nie otrzymamy krótszej ścieżki z do niż ta dotychczas znaleziona. Jeżeli tak, to aktualizowane są także wartości i . W celu relaksacji krawędzi używamy procedury RELAKSUJ.

Algorytm Relaksacja krawędzi


 RELAKSUJ
 1  if  then
 3  begin
 4    
 5    
 6  end

Algorytm

Po przypomnieniu czym była relaksacja gotowi jesteśmy na zapisanie algorytmu Bellmana-Forda, a następnie udowodnienie jego poprawności.

Algorytm Bellmana-Forda


 BELLMAN-FORD
 1  INICJUJ
 2  for  to  do
 3    for każda krawędź  do
 4      RELAKSUJ
 5  for każda krawędź  do
 6    if ' then
 7      return NIL
 8  return (d,\pi)

Poniższa animacja przedstawia działanie algorytmu dla grafu o pięciu wierzchołkach.

<flash>file=Zasd_animacja_bellman_ford1.swf|width=660|height=250</flash>

Algorytm ten działa w czasie , co łatwo pokazać gdyż:

  • proces inicjacji w linii 1 zajmuje czas ,
  • w każdym z przebiegów głównej pętli w linii 2 algorytmu przeglądane są wszystkie krawędzie grafu w linii 3 , co zajmuje czas ,
  • końcowa pętla algorytmu w liniach 5-7 działa w czasie .

Poprawność

Dowód poprawności algorytmu Bellmana-Forda zaczniemy od pokazania, że algorytm działa poprawnie przy założeniu, że w grafie nie ma cykli o ujemnych wagach.

Lemat 1

Niech będzie grafem skierowanym i niech funkcja zadaje wagi krawędzi. Niech będzie wierzchołkiem z którego liczymy odległości algorytmem Bellmana-Forda. Jeżeli w grafie nie ma cykli o ujemnej wadze osiągalnych z , to algorytm poprawnie oblicza odległości, tzn. na koniec działania algorytmu dla każdego wartość jest odległością w z do .

Dowód

Oznaczmy przez odległość z wierzchołka do w grafie . Niech będzie wierzchołkiem osiągalnym ze źródła i niech oznacza najkrótszą ścieżkę z do , gdzie oraz . Ścieżka ta jest ścieżką prostą, bo najkrótsze ścieżki muszą być proste, więc . Pokażemy teraz indukcyjnie, że poczynając od -tego przebiegu zachodzi dla . W algorytmie wykonujemy obrotów pętli oraz , co oznacza, że z tej tezy indukcyjnej wynika poprawność algorytmu.

Zauważmy, że teza indukcyjna zachodzi po inicjacji algorytmu, gdyż Załóżmy, że teza indukcyjna zachodzi dla kroku 'tego. Ponieważ ścieżki dla są najkrótsze jako podścieżki ścieżki , to po wykonaniu pętli wartości dla się nie zmienią. Pozostaje nam więc do pokazania to, że wartość będzie dobrze policzona. W przebiegu wykonujemy między innymi relaksację krawędzi . Ponieważ jest dobrze policzone, to po tej relaksacji wyznaczona będzie także poprawnie wartość , bo założyliśmy, że najkrótsza ścieżka do przechodzi przez .

Pozostaje nam jedynie zastanowić się co się dzieje gdy wierzchołek nie jest osiągalny z . Musi wtedy zachodzić pod koniec działania algorytmu. Gdyby tak nie było to oznaczałoby, z właściwości procedury RELAKSUJ, że istnieje ścieżka od do . Sprzeczność. End of proof.gif


Dowód

Dowód ten można przeprowadzić w podobny sposób do dowodu Lematu 1.

End of proof.gif

Twierdzenie 3

Niech będzie grafem skierowanym i niech funkcja zadaje wagi krawędzi. Załóżmy, że algorytm Bellmana-Forda został wykonany dla wierzchołka . Jeżeli graf zawiera cyklu o ujemnej wadze osiągalny ze źródła to algorytm zwraca wartość NIL, w przeciwnym wypadku jest odległością z do , a wyznacza drzewo najkrótszych ścieżek o korzeniu w .


{{dowod|||3=Załóżmy najpierw, że graf nie zawiera cykli o ujemnej wadze, które byłyby osiągalne z . Wtedy z Lematu 1 wiemy, że są poprawnie policzonymi odległościami. Jeżeli odległości zostały poprawnie policzone przez funkcję RELAKSUJ to koduje najkrótsze ścieżki w grafie. Wynika to z właściwości [[#algorytm_relaksacja_krawędzi|funkcji RELAKSUJ], która wyliczając odległość wyznaczą jednocześnie przez jaki wierzchołek prowadzi ta najkrótsza ścieżka.

Musimy teraz pokazać, że algorytm poprawnie wykrywa, czy w grafie istnieje cykl ujemnej długości osiągalny z . Jeżeli nie ma takiego cyklu to wtedy są poprawnie policzone przed wykonaniem testu w liniach 5-8 algorytmu Bellmana-Forda. W takim razie zachodzi:



Powyższa nierówność zachodzi ponieważ jest ścieżką w grafie, a więc jest nie krótsza niż najkrótsza ścieżka . Widzimy więc, że w tym przypadku żaden z testów w linijce 6 algorytmu nie będzie spełniony i algorytm nie zwróci NIL.

Załóżmy teraz, że w grafie istnieje cykl o ujemnej wadze osiągalny z . Oznaczmy ten cykl jako , gdzie . Dla cyklu tego mamy:

     (1)

Gdyby w tej sytuacji algorytm Bellmana-Forda nie zwrócił wartości NIL to dla każdej krawędzi musiałaby zachodzić nierówność . Sumując tą nierówność stronami po wszystkich otrzymujemy.



ponieważ to



Wiemy, że cykl jest osiągalny a zatem dla każdego mamy . Możemy więc skrócić po obydwu stronach równania i otrzymujemy:



co stoi w sprzeczności z nierównością (1). Jeżeli więc w grafie istnieje cykl o ujemnej wadze osiągalny z , to algorytm zwróci NIL. }}