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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m (Zastępowanie tekstu – „<math> ” na „<math>”)
 
(Nie pokazano 121 wersji utworzonych przez 3 użytkowników)
Linia 1: Linia 1:
== Abstrakt ==
== Abstrakt ==


Pierwsza część tego wykładu poświęcona będzie problemowi obliczania
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 <math>O(|V||E|)</math>. 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.
najkrótszych ścieżek w grafie z jednego źródła w przypadku, w którym
 
wagi krawędzi mogą być ujemne. Zaprezentujemy algorytm
== Definicja problemu ==
Bellmana-Forda, który rozwiązuje ten problem w czasie
 
<math>O(|V||E|)</math>. W drugiej części zajmiemy się problemem
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 <math>G = (V,E)</math>, funkcję <math>w: E \to \mathcal{R}</math> przypisującą wagi krawędziom oraz jeden wybrany wierzchołek <math>s</math>. {{kotwica|waga_ścieżki|'''Wagę'''|}} ścieżki <math>p=(v_0,v_1,\ldots,v_k)</math> definiujemy jako wagę tworzących ją krawędzi:
obliczania odległości między wszystkimi parami wierzchołków.
 
Pokażemy związki tego problemu z mnożeniem macierzy.
 
{{wzor2|1=
<math>
w(p) = \sum_{i=0}^{k-1} w(v_{i}, v_{i+1}).
</math>}}
 
 
{{kotwica|odległość|'''Odległość'''}} z wierzchołka <math>u</math> do wierzchołka <math>v</math> definiujemy jako
 
{{wzor2|1=
<math>
\delta(u,v) = \begin{cases}
\min\{w(p): p \mbox{ ścieżka z } u \mbox{ do } v\}, & \mbox{jeżeli istnieje ścieżka z } u \mbox{ do } v,\\
\infty & \mbox{w przeciwnym przypadku.}
\end{cases}
</math>
}}
 
{{kotwica|najkrótsza_ścieżka|'''Najkrótszą ścieżką'''}} z wierzchołka <math>u</math> do wierzchołka <math>v</math> jest każda ścieżka <math>p</math> z <math>u</math> do <math>v</math>, której waga <math>w(p)</math> jest równa odległości <math>\delta(u,v)</math> z <math>u</math> do <math>v</math>.
 
{{kotwica|problem_sssp|'''W problemie najkrótszych ścieżek z jednego wierzchołka'''}} chcemy obliczyć odległości <math>\delta(s,v)</math> dla wszystkich wierzchołków <math>v\in V</math> wraz z drzewem najkrótszych ścieżek z <math>s</math>. {{kotwica|drzewo_najkrótszych_ścieżek|'''Drzewem najkrótszych ścieżek'''}} o korzeniu w <math>s</math>  nazywamy podgraf skierowany <math>G' = (V', E')</math>, w którym <math>V' \subseteq V</math>, <math>E' \subseteq E</math> taki, że:
* <math>V'</math> jest zbiorem wierzchołków w <math>G</math> do których istnieje ścieżka z <math>s</math>,
* <math>G'</math> jest drzewem którego korzeniem jest <math>s</math>,
* dla każdego wierzchołka <math>v\in V'</math> jedyna ścieżka z <math>s</math> do <math>v</math> w grafie <math>G'</math> jest najkrótszą ścieżką z <math>s</math> do <math>v</math> w grafie <math>G</math>.
 
W naszych algorytmach drzewo najkrótszych ścieżek będziemy reprezentować jako {{kotwica|funkcja_poprzedników|'''funkcję poprzedników'''}} <math>\pi:V \to V</math>, określającą poprzednika wierzchołka <math>v</math> w drzewie najkrótszych ścieżek. Drzewo najkrótszych ścieżek <math>G_{\pi}=(V_{\pi},E_{\pi})</math> możemy uzyskać z <math>\pi</math> w następujący sposób:
 
{{wzor2|1=
<math>V_{\pi} = \{v \in V : \pi(v) \neq NIL\} \cup \{s\}</math>,
}}
 
{{wzor2|1=<math>
E_{\pi} = \{(\pi(v),v) \in E: v \in V_{\pi} - \{s\}\}.
</math>
}}


== Algorytm Bellmana-Forda ==
== Algorytm Bellmana-Forda ==
{{kotwica|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 <math>G=(V,E)</math> i funkcję wagową <math>w:E \to \mathcal{R}</math>. Algorytm Bellmana-Forda wylicza dla zadanego wierzchołka <math>s</math>, czy istnieje w grafie <math>G</math> cykl o ujemnej wadze osiągalny z <math>s</math>. Jeżeli taki cykl nie istnieje, algorytm oblicza najkrótsze ścieżki z <math>s</math> do wszystkich pozostałych
wierzchołków wraz z ich wagami.
=== Relaksacja ===
Podobnie jak to było w [[Algorytmy i struktury danych/ASD Moduł 11#algorytm_dijkstry|Algorytmie Dijkstry]], użyjemy metody relaksacji. W metodzie tej utrzymujemy dla każdego wierzchołka <math>v \in V</math> wartość <math>d(v)</math>, będącą górnym ograniczeniem wagi najkrótszej ścieżki z <math>s</math> do <math>v</math>. W algorytmie utrzymywać będziemy także dla każdego wierzchołka <math>v</math> wskaźnik <math>\pi(v)</math> 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|algorytm_inicjacja_sssp|
  INICJACJA<math>(G,s)</math>
  1  '''for''' każdy wierzchołek <math>v\in V</math> '''do'''
  2  '''begin'''
  3    <math>d(v) = \infty</math>
  4    <math>\pi(v) = NIL</math>
  5  '''end'''
  6  <math>d(s) = 0</math>
  7  '''return''' <math>(d,\pi)</math>
}}
Ustalone przez tą procedurę wartości <math>d(v)</math> są dobrymi ograniczeniami górnymi na odległości w grafie.
{{kotwica|relaksacja|'''Relaksacja'''}} krawędzi <math>(u,v)</math> polega na sprawdzeniu, czy przechodząc krawędzią <math>(u,v)</math> z <math>u</math> do <math>v</math>, nie otrzymamy krótszej ścieżki z <math>s</math> do <math>v</math> niż ta dotychczas znaleziona. Jeżeli tak, to aktualizowane są także wartości <math>d(v)</math> i <math>\pi(v)</math>. W celu relaksacji krawędzi <math>(u,v)</math> używamy następującej procedury nazwanej tutaj RELAKSUJ.
{{algorytm|Relaksacja krawędzi|algorytm_relaksacja_krawędzi|
  RELAKSUJ<math>(u,v,w,d,\pi)</math>
  1  '''if''' <math>d(v) > d(u) + w(u,v)</math> '''then'''
  3  '''begin'''
  4    <math>d(v) = d(u) + w(u,v)</math>
  5    <math>\pi(v) = u</math>
  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|algorytm_Bellmana-Forda|
  BELLMAN-FORD<math>(G,w,s)</math>
  1  <math>(d,\pi)=</math>[[#algorytm_inicjacja_sssp|INICJUJ]]<math>(G,s)</math>
  2  '''for''' <math>i=1</math> '''to''' <math>|V|-1</math> '''do'''
  3    '''for''' każda krawędź <math>(u,v) \in E</math> '''do'''
  4      [[#algorytm_relaksacja_krawędzi|RELAKSUJ]]<math>(u,v,w,d,\pi)</math>
  5  '''for''' każda krawędź <math>(u,v) \in E</math> '''do'''
  6    '''if''' '<math>d(v)>d(u) + w(u,v)</math> '''then'''
  7      '''return''' <math>NIL</math>
  8  '''return''' <math>(d,\pi)</math>
}}
Poniższa animacja przedstawia działanie algorytmu dla grafu o pięciu wierzchołkach. <center><flash>file=Zasd_animacja_bellman_ford1.swf|width=660|height=250</flash></center>
Algorytm ten działa w czasie <math>O(|V||E|)</math>, co łatwo pokazać, gdyż:
* proces inicjacji w linii 1 zajmuje czas <math>O(|V|)</math>,
* w każdym z <math>|V|</math> przebiegów głównej pętli w linii 2 algorytmu przeglądane są wszystkie krawędzie grafu w linii 3 , co zajmuje czas <math>O(|V||E|)</math>,
* końcowa pętla algorytmu w liniach 5-7 działa w czasie <math>O(|E|)</math>.


'''Algorytm Bellmana-Forda''' służy do rozwiązania problemu
=== Poprawność ===
znalezienia najkrótszych ścieżek w grafie, w którym wagi krawędzi
 
mogą być ujemne. W problemie tym mamy dany graf <math>G=(V,E)</math>
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.
i funkcję wagową <math>w:E \to \mathcal{R}</math>. Algorytm
Bellmana-Forda wylicza dla zadanego wierzchołka <math>s</math>, czy
istnieje w grafie <math>G</math> cykl o ujemnej wadze osiągalny z
<math>s</math>. Jeżeli taki cykl nie istniej to algorytm oblicza
najkrótsze ścieżki z <math>s</math> do wszystkich pozostałych
wierzchołków wraz z ich wagami.


== Relaksacja ==
{{lemat|1|bf_poprawnosc_1|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. Niech <math>s</math> 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 <math>s</math>, to algorytm poprawnie oblicza odległości, tzn. na koniec działania algorytmu dla każdego <math>v \in V</math> wartość <math>d(v)</math> jest odległością w <math>G</math> z <math>s</math> do <math>v</math>.
}}


Podobnie ja to było w [[algorytm_dijkstry|Algorytmie Dijkstry]]
{{dowod|||3=Oznaczmy przez <math>\delta(v,u)</math> odległość z wierzchołka <math>v</math> do <math>u</math> w grafie <math>G</math>. Niech <math>v</math> będzie wierzchołkiem osiągalnym ze źródła <math>s</math> i niech <math>p = (v_0, v_1, \ldots, v_k)</math> oznacza najkrótszą ścieżkę z <math>s</math> do <math>v</math>, gdzie <math>v_0 = s</math> oraz <math>v_k = v</math>. Ścieżka ta jest ścieżką prostą, bo najkrótsze ścieżki muszą być proste, więc <math>k\le |V|-1</math>. Pokażemy teraz indukcyjnie, że poczynając od <math>i</math>-tego przebiegu zachodzi <math>d(v_i) = \delta(s,v_i)</math> dla <math>i = 0,1,\ldots, k</math>. W algorytmie wykonujemy <math>|V|-1</math> obrotów pętli oraz <math>k \le |V|-1</math>, co oznacza, że z tej tezy indukcyjnej wynika poprawność algorytmu.
użyjemy metody relaksacji. Metoda ta polega na tym, że w trakcie
działania algorytmu dla każdego wierzchołka <math>v \in V</math>
utrzymujemy wartość <math>d(v)</math> będącą górnym ograniczeniem
wagi najkrótszej ścieżki ze <math>s</math> do <math>v</math>. W
algorytmie utrzymywać będziemy także dla każdego wierzchołka
<math>v</math> wskaźnik <math>\pi(v)</math> 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
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> 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> przebiegu wykonujemy między innymi relaksację krawędzi <math>(v_{k}, v_{k+1})</math>. Ponieważ <math>d(v_k)</math> jest dobrze policzone, 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>.
następującej procedury:


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, oznaczałoby to, 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ść.
}}


{{algorytm|Inicjalizacja algorytmu najkrótszych ścieżek|algorytm_inicjalizacjia_sssp|
{{twierdzenie|2|bf_poprawnosc|3=
  INICJALIZUJ<math>(G,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 cykl 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>.
  '''for''' każdy wierzchołek <math>v\in V</math> '''do'''
    <math>d(v) = \infty</math>
    <math>\pi(v) = NIL</math>
  <math>d(s) = 0</math>
}}
}}




Ustalone przez tą procedure wartości <math>d(v)</math> są dobrymi ograniczeniami
{{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ść wyznacza jednocześnie, przez jaki wierzchołek prowadzi ta najkrótsza ścieżka.
górnymi na odległości.
 
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, 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:
 
 
{{wzor2|1=<math>
d(v) = \delta(s,v) \le \delta(s,u) + w(u,v) = d(u) + w(u,v).
</math>}}
 
 
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:
 
{{wzor|wzor_cykl|1|
<math>
\sum_{i=0}^{k-1} w(v_{i},v_{i+1}) <0.
</math>}}
 
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:
 
 
{{wzor2|1=<math>
\sum_{i=0}^{k-1} \left[d(v_i) + w(v_i, v_{i+1})\right] \ge \sum_{i=0}^{k-1} d(v_{i+1})</math>,}}
 
{{wzor2|1=<math>
\sum_{i=0}^{k-1} d(v_i) + \sum_{i=0}^{k-1} w(v_i, v_{i+1}) \ge \sum_{i=1}^{k} d(v_{i})</math>,}}
 
 
ponieważ <math>v_0 = v_k</math> to
 
 
{{wzor2|1=<math>
\sum_{i=0}^{k-1} d(v_i) + \sum_{i=0}^{k-1} w(v_i, v_{i+1}) \ge \sum_{i=0}^{k-1} d(v_{i}).
</math>}}
 
 
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:


relaksacja|Relaksacja]] krawędzi <math>(u,v)</math> polega na
 
sprawdzeniu, czy przechodząc krawędzią <math>(u,v)</math> z
{{wzor2|1=<math>
<math>u</math> do <math>v</math>, nie otrzymamy krótszej ścieżki z
\sum_{i=0}^{k-1} w(v_i, v_{i+1}) \ge 0</math>,}}
<math>s</math> do <math>v </math>niż ta dotychczas znaleziona.
 
Jeżeli tak to aktualizowane są także wartości <math>d(v)</math> i
 
<math>\pi(v)</math>. W celu relaksacji krawędzi <math>(u,v)</math>
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>.
używamy procedury
}}

Aktualna wersja na dzień 22:16, 11 wrz 2023

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 , Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle E' \subseteq E} taki, że:

  • Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle V'} jest zbiorem wierzchołków w Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle G} do których istnieje ścieżka z Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle s} ,
  • Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle G'} jest drzewem którego korzeniem jest Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle s} ,
  • dla każdego wierzchołka Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle v\in V'} jedyna ścieżka z Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle s} do Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle v} w grafie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle G'} jest najkrótszą ścieżką z Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle s} do Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle v} w grafie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle G} .

W naszych algorytmach drzewo najkrótszych ścieżek będziemy reprezentować jako funkcję poprzedników Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \pi:V \to V} , określającą poprzednika wierzchołka Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle v} w drzewie najkrótszych ścieżek. Drzewo najkrótszych ścieżek Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle G_{\pi}=(V_{\pi},E_{\pi})} możemy uzyskać z Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \pi} w następujący sposób:

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle V_{\pi} = \{v \in V : \pi(v) \neq NIL\} \cup \{s\}} ,
Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle E_{\pi} = \{(\pi(v),v) \in E: v \in V_{\pi} - \{s\}\}. }

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 Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle G=(V,E)} i funkcję wagową Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle w:E \to \mathcal{R}} . Algorytm Bellmana-Forda wylicza dla zadanego wierzchołka Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle s} , czy istnieje w grafie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle G} cykl o ujemnej wadze osiągalny z Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle s} . Jeżeli taki cykl nie istnieje, algorytm oblicza najkrótsze ścieżki z Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle s} do wszystkich pozostałych wierzchołków wraz z ich wagami.

Relaksacja

Podobnie jak to było w Algorytmie Dijkstry, użyjemy metody relaksacji. W metodzie tej utrzymujemy dla każdego wierzchołka Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle v \in V} 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 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, 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, oznaczałoby to, 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 cykl 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ść wyznacza 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, 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
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Zaawansowane_algorytmy_i_struktury_danych/Wykład_5&oldid=82605”