Zaawansowane algorytmy i struktury danych/Wykład 5: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 113: Linia 113:
 
Zauważmy, że teza indukcyjna zachodzi po inicjacji algorytmu, gdyż <math>d(v_0) = d(s) = 0</math> i <math>\delta(s,s) = \delta(s,v_0)</math>. Załóżmy, że teza indukcyjna zachodzi dla kroku <math>k</math>'tego. Ponieważ ścieżki <math>p = (v_0, v_1, \ldots, v_i)</math> dla <math>i \le k</math> są najkrótsze jako podścieżki  ścieżki <math>p</math>, to po <math>k+1</math>'wszym wykonaniu pętli wartości <math>d(v_i)</math> dla <math>i \le k</math> się nie zmienią. Pozostaje nam więc do pokazania to, że wartość <math>d(v_{k+1})</math> będzie dobrze policzona. W <math>k+1</math>'wszym przebiegu wykonujemy między innymi relaksację krawędzi <math>(v_{k}, v_{k+1})</math>.  Ponieważ <math>d(v_k)</math> jest dobrze policzone, to po tej relaksacji wyznaczona będzie także poprawnie wartość <math>d(v_{k+1})</math>, bo założyliśmy, że najkrótsza ścieżka do <math>v_{k+1}</math> przechodzi przez <math>v_k</math>.
 
Zauważmy, że teza indukcyjna zachodzi po inicjacji algorytmu, gdyż <math>d(v_0) = d(s) = 0</math> i <math>\delta(s,s) = \delta(s,v_0)</math>. Załóżmy, że teza indukcyjna zachodzi dla kroku <math>k</math>'tego. Ponieważ ścieżki <math>p = (v_0, v_1, \ldots, v_i)</math> dla <math>i \le k</math> są najkrótsze jako podścieżki  ścieżki <math>p</math>, to po <math>k+1</math>'wszym wykonaniu pętli wartości <math>d(v_i)</math> dla <math>i \le k</math> się nie zmienią. Pozostaje nam więc do pokazania to, że wartość <math>d(v_{k+1})</math> będzie dobrze policzona. W <math>k+1</math>'wszym przebiegu wykonujemy między innymi relaksację krawędzi <math>(v_{k}, v_{k+1})</math>.  Ponieważ <math>d(v_k)</math> jest dobrze policzone, to po tej relaksacji wyznaczona będzie także poprawnie wartość <math>d(v_{k+1})</math>, bo założyliśmy, że najkrótsza ścieżka do <math>v_{k+1}</math> przechodzi przez <math>v_k</math>.
  
Pozostaje nam jedynie zastanowić się, co się dzieje, gdy wierzchołek <math>v</math> nie jest osiągalny z <math>s</math>. Musi wtedy zachodzić <math>d(v) = \infty</math> pod koniec działania algorytmu. Gdyby tak nie było to oznaczałoby, z właściwości procedury [[#algorytm_relaksacja_krawędzi|RELAKSUJ]], że istnieje ścieżka od <math>s</math> do <math>v</math>. Sprzeczność.
+
Pozostaje nam jedynie zastanowić się, co się dzieje, gdy wierzchołek <math>v</math> nie jest osiągalny z <math>s</math>. Musi wtedy zachodzić <math>d(v) = \infty</math> pod koniec działania algorytmu. Gdyby tak nie było to oznaczałoby, z właściwości procedury [[#algorytm_relaksacja_krawędzi|RELAKSUJ]], że istnieje ścieżka od <math>s</math> do <math>v</math>, co daje sprzeczność.
 
}}
 
}}
  
 
+
{{twierdzenie|2|bf_poprawnosc|3=
{{dowod|||
 
Dowód ten można przeprowadzić w podobny sposób do dowodu [[#bf_poprawnosc_1|Lematu 1]].
 
}}
 
 
 
{{twierdzenie|3|bf_poprawnosc|3=
 
 
Niech <math>G = (V,E)</math> będzie grafem skierowanym i niech funkcja <math>w:E \to \mathcal{R}</math> zadaje wagi krawędzi. Załóżmy, że algorytm Bellmana-Forda został wykonany dla wierzchołka <math>s</math>. Jeżeli graf zawiera cyklu o ujemnej wadze osiągalny ze źródła <math>s</math> to algorytm zwraca wartość NIL, w przeciwnym wypadku <math>d(v)</math> jest odległością z <math>s</math> do <math>v</math>, a <math>\pi(v)</math> wyznacza drzewo najkrótszych ścieżek o korzeniu w <math>s</math>.
 
Niech <math>G = (V,E)</math> będzie grafem skierowanym i niech funkcja <math>w:E \to \mathcal{R}</math> zadaje wagi krawędzi. Załóżmy, że algorytm Bellmana-Forda został wykonany dla wierzchołka <math>s</math>. Jeżeli graf zawiera cyklu o ujemnej wadze osiągalny ze źródła <math>s</math> to algorytm zwraca wartość NIL, w przeciwnym wypadku <math>d(v)</math> jest odległością z <math>s</math> do <math>v</math>, a <math>\pi(v)</math> wyznacza drzewo najkrótszych ścieżek o korzeniu w <math>s</math>.
 
}}
 
}}
  
  
{{dowod|||3=Załóżmy najpierw, że graf nie zawiera cykli o ujemnej wadze, które byłyby osiągalne z <math>s</math>. Wtedy z [[#bf_poprawnosc_1|Lematu 1]] wiemy, że <math>d(v)</math> są poprawnie policzonymi odległościami. Jeżeli odległości <math>d(v)</math> zostały poprawnie policzone przez [[#algorytm_relaksacja_krawędzi| funkcję RELAKSUJ]] to <math>\pi(v)</math> 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.
+
{{dowod|||3=Załóżmy najpierw, że graf nie zawiera cykli o ujemnej wadze, które byłyby osiągalne z <math>s</math>. Wtedy z [[#bf_poprawnosc_1|Lematu 1]] wiemy, że <math>d(v)</math> są poprawnie policzonymi odległościami. Jeżeli odległości <math>d(v)</math> zostały poprawnie policzone przez [[#algorytm_relaksacja_krawędzi| funkcję RELAKSUJ]] to <math>\pi(v)</math> 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 <math>G</math> istnieje cykl ujemnej długości osiągalny z <math>s</math>. Jeżeli nie ma takiego cyklu to wtedy <math>d(v)</math> są poprawnie policzone przed wykonaniem testu w liniach 5-8 [[#algorytm_Bellmana-Forda|algorytmu Bellmana-Forda]]. W takim razie zachodzi:
 
Musimy teraz pokazać, że algorytm poprawnie wykrywa, czy w grafie <math>G</math> istnieje cykl ujemnej długości osiągalny z <math>s</math>. Jeżeli nie ma takiego cyklu to wtedy <math>d(v)</math> są poprawnie policzone przed wykonaniem testu w liniach 5-8 [[#algorytm_Bellmana-Forda|algorytmu Bellmana-Forda]]. W takim razie zachodzi:
Linia 136: Linia 131:
  
  
Powyższa nierówność zachodzi ponieważ <math>s \to u \to v</math> jest ścieżką w grafie, a więc jest nie krótsza niż najkrótsza ścieżka <math>s \to v</math>. 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.
+
Powyższa nierówność zachodzi ponieważ <math>s \to u \to v</math> jest ścieżką w grafie, a więc jest nie krótsza niż najkrótsza ścieżka <math>s \to v</math>. 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 <math>NIL</math>.
  
 
Załóżmy teraz, że w grafie <math>G</math> istnieje cykl  o ujemnej wadze osiągalny z <math>s</math>. Oznaczmy ten cykl jako <math>c =(v_0, v_1,\ldots, v_k)</math>, gdzie <math>v_0 = v_k</math>. Dla cyklu tego mamy:
 
Załóżmy teraz, że w grafie <math>G</math> istnieje cykl  o ujemnej wadze osiągalny z <math>s</math>. Oznaczmy ten cykl jako <math>c =(v_0, v_1,\ldots, v_k)</math>, gdzie <math>v_0 = v_k</math>. Dla cyklu tego mamy:
Linia 142: Linia 137:
 
{{wzor|wzor_cykl|1|
 
{{wzor|wzor_cykl|1|
 
<math>
 
<math>
\sum_{i=0}^{k} w(v_{i},v_{i+1}) <0.
+
\sum_{i=0}^{k-1} w(v_{i},v_{i+1}) <0.
 
</math>}}
 
</math>}}
  
Gdyby w tej sytuacji [[#algorytm Bellmana-Forda| algorytm Bellmana-Forda]] nie zwrócił wartości NIL to dla każdej krawędzi <math>(v_i, v_{i+1})</math> musiałaby zachodzić nierówność <math>d(v_{i}) + w(v_i, v_{i+1}) \ge d(v_{i+1}) </math>. Sumując tą nierówność stronami po wszystkich <math>i = 0,\ldots, k-1</math> otrzymujemy.
+
Gdyby w tej sytuacji [[#algorytm Bellmana-Forda| algorytm Bellmana-Forda]] nie zwrócił wartości <math>NIL</math> to dla każdej krawędzi <math>(v_i, v_{i+1})</math> musiałaby zachodzić nierówność <math>d(v_{i}) + w(v_i, v_{i+1}) \ge d(v_{i+1}) </math>. Sumując tą nierówność stronami po wszystkich <math>i = 0,\ldots, k-1</math> otrzymujemy.
  
  
Linia 165: Linia 160:
  
  
Wiemy, że cykl <math>c</math> jest osiągalny a zatem dla każdego <math>i = 0,\ldots,k</math> mamy <math>d(v)<\infty</math>. Możemy więc skrócić <math>\sum_{i=0}^{k-1} d(v_i)</math> po obydwu stronach równania i otrzymujemy:
+
Wiemy, że cykl <math>c</math> jest osiągalny z <math>s</math>, a zatem dla każdego <math>i = 0,\ldots,k</math> mamy <math>d(v)<\infty</math>. Możemy więc skrócić <math>\sum_{i=0}^{k-1} d(v_i)</math> po obydwu stronach nierówności otrzymując:
  
  
Linia 173: Linia 168:
  
  
co stoi w sprzeczności z [[#wzor_cykl|nierównością (1)]]. Jeżeli więc w grafie istnieje cykl o ujemnej wadze osiągalny z <math>s</math>, to algorytm zwróci NIL.
+
co stoi w sprzeczności z [[#wzor_cykl|nierównością (1)]]. Jeżeli więc w grafie istnieje cykl o ujemnej wadze osiągalny z <math>s</math>, to algorytm zwróci <math>NIL</math>.
 
}}
 
}}

Wersja z 09:42, 19 wrz 2006

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 w grafie.

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 następującej procedury nazwanej tutaj 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 
 8  return 

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ż i . Załóżmy, że teza indukcyjna zachodzi dla kroku 'tego. Ponieważ ścieżki dla są najkrótsze jako podścieżki ścieżki , to po 'wszym wykonaniu pętli wartości dla się nie zmienią. Pozostaje nam więc do pokazania to, że wartość będzie dobrze policzona. W 'wszym 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 , co daje sprzeczność. End of proof.gif

Twierdzenie 2

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 .


Dowód

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 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 .

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 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 z , a zatem dla każdego mamy . Możemy więc skrócić po obydwu stronach nierówności otrzymując:



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 . End of proof.gif