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

Wersja z 17:35, 20 lip 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 $O (| V | | E |)$ . 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 $G = (V, E)$ , funkcję $w : E \to ℛ$ przypisującą wagi krawędziom oraz jeden wybrany wierzchołek $s$ . Wagę ścieżki $p = (v_{0}, v_{1}, \dots, v_{k})$ definiujemy jako wagę tworzących ją krawędzi:

w (p) = \sum_{i = 0}^{k - 1} w (v_{i}, v_{i + 1}) .

Odległość z wierzchołka $u$ do wierzchołka $v$ definiujemy jako

δ (u, v) = {\begin{cases} \min {w (p) : p ścieżka z u do v}, & jeżeli istnieje ścieżka z u do v, \\ \infty & w przeciwnym przypadku. \end{cases}

Najkrótszą ścieżką z wierzchołka $u$ do wierzchołka $v$ jest każda ścieżka $p$ z $u$ do $v$ , której waga $w (p)$ jest równa odległości $δ (u, v)$ z $u$ do $v$ .

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 $G = (V, E)$ i funkcję wagową $w : E \to ℛ$ . Algorytm Bellmana-Forda wylicza dla zadanego wierzchołka $s$ , czy istnieje w grafie $G$ cykl o ujemnej wadze osiągalny z $s$ . Jeżeli taki cykl nie istniej to algorytm oblicza najkrótsze ścieżki z $s$ do wszystkich pozostałych wierzchołków wraz z ich wagami.

Relaksacja

Podobnie ja to było w Algorytmie Dijkstry użyjemy metody relaksacji. Metoda ta polega na tym, że w trakcie działania algorytmu dla każdego wierzchołka $v \in V$ utrzymujemy wartość $d (v)$ będącą górnym ograniczeniem wagi najkrótszej ścieżki ze $s$ do $v$ . W algorytmie utrzymywać będziemy także dla każdego wierzchołka $v$ wskaźnik $π (v)$ 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 $(G, s)$ 
   for każdy wierzchołek  $v \in V$  do
      $d (v) = \infty$ 
      $π (v) = N I L$ 
    $d (s) = 0$

Ustalone przez tą procedure wartości $d (v)$ są dobrymi ograniczeniami górnymi na odległości.

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

Algorytm Relaksacja krawędzi

 RELAKSUJ $(u, v, w)$ 
   if  $d (v) > d (u) + w (u, v)$  then
      $d (v) = d (u) + w (u, v)$ 
      $π (v) = u$

Algorytm

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

Algorytm Bellmana-Forda

 BELLMAN-FORD $(G, w, s)$ 
 1  INICJUJ $(G, s)$ 
 2  for  $i = 1$  to  $| V | - 1$  do
 3    for każda krawędź  $(u, v) \in E$  do
 4      RELAKSUJ $(u, v, w)$ 
 5  for każda krawędź  $(u, v) \in E$  do
 6    if ' $d (v) > d (u) + w (u, v)$  then
 7      return FALSE
 8  return TRUE

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

Algorytm ten działa w czasie $O (| V | | E |)$ , co jest łatwo pokazać gdyż:

proces inicjacji linia 1 zajmuje czas $O (| V |)$ ,
w każdym z $| V |$ przebiegów głównej pętli w lini 2 algorytmu przeglądane są wszystkie krawędzie grafu w linie 3 , co zajmuje czas $O (| V | | E |)$ ,
końcowa pętla algorytmu linie 5-7 działa w czasie $O (| E |)$ .

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

G = (V, E)

będzie grafem skierowanym i niech funkcja

w : E \to ℛ

zadaje wagi krawędzi. Niech

s

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

s

, to algorytm poprawnie oblicza odległości, tzn. na koniec działania algorytmu dla każdego

v \in V

wartość

d (v)

jest odległością w

G

z

s

do

v

.

Dowód

Oznaczmy przez

δ (v, u)

odległość z wierzchołka

v

do

u

w grafie

G

. Niech

v

będzie wierzchołkiem osiągalnym ze źródła

s

i niech

p = (v_{0}, v_{1}, \dots, v_{k})

oznacza najkrótszą ścieżkę z

s

do

v

, gdzie

v_{0} = s

oraz

v_{k} = v

. Ścieżka ta jest ścieżką prostą, bo najkrótsze ścieżki muszą być proste, więc

k \leq | V | - 1

. Pokażemy teraz indukcyjnie, że poczynając od

i

-tego przebiegu zachodzi

d (v_{i}) = δ (s, v_{i})

dla

i = 0, 1, \dots, k

. W algorytmie wykonujemy

| V | - 1

obrotów pętli oraz

k \leq | V | - 1

, co oznacza, że z tej tezy indukcyjnej wynika poprawność algorytmu.

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

Pozostaje nam jedynie zastanowić się co się dzieje gdy wierzchołek

v

nie jest osiągalny z

s

. Musi wtedy zachodzić

d (v) = \infty

pod koniec działania algorytmu. Gdyby tak nie było to oznaczało by, z właściwości procedury RELAKSUJ, że istnieje ścieżka od

s

do

v

. Sprzeczność.

Dowód

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

Twierdzenie 3

Niech

G = (V, E)

będzie grafem skierowanym i niech funkcja

w : E \to ℛ

zadaje wagi krawędzi. Załóżmy, że algorytm Bellmana-Forda został wykonany dla wierzchołka

s

. Jeżeli graf nie zawiera cyklu o ujemnej wadze osiągalnego ze źródła

s

to algorytm zwraca wartość TRUE,

d (v)

jest odległością z

s

do

v

, a

π (v)

wyznacza drzewo najkrótszych ścieżek o korzeniu w

s

. Jeżeli natomiast

G

zawiera cykl o ujemnej wadze osiągalny ze źródła to algorytm zwraca wartość FALSE.

Dowód

Załóżmy najpierw, że graf nie zawiera cykli o ujemnej wadze, które byłyby osiągalne z

s

. Wtedy z Lematu 1 wiemy, że

d (v)

są poprawnie policzonymi odległościami. Jeżeli odległości

d (v)

zostały poprawnie policzone przez funkcję RELAKSUJ to

π (v)

koduje najkrótsze ścieżki w grafie. Wynika to z właściwości funkcji RELAKSUJ relaks, 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 $G$ istnieje cykl ujemnej długości osiągalny z $s$ . Jeżeli nie ma takiego cyklu to wtedy $d (v)$ są poprawnie policzone przed wykonaniem testu w liniach 5-8 Algorytmu Bellmana-Forda. W takim razie zachodzi:

d (v) = δ (s, v) \leq δ (s, u) + w (u, v) = d (u) + w (u, v) .

Powyższa nierówność zachodzi ponieważ Parser nie mógł rozpoznać (nieznana funkcja „\rightsquidarrow”): {\displaystyle s \rightsquidarrow u \rightsquidarrow v} jest ścieżką w grafie, a więc jest nie krótsza niż najkrótsza ścieżka Parser nie mógł rozpoznać (nieznana funkcja „\rightdquidarrow”): {\displaystyle s \rightdquidarrow v} . Widzimy więc, że w tym przypadku żaden z testów w linijce 6 algorytmu nie będzie spełniony i algorytm zwróci TRUE.

Załóżmy teraz, że w grafie $G$ istnieje cykl o ujemnej wadze osiągalny z $s$ . Oznaczmy ten cykl jako $c = (v_{0}, v_{1}, \dots, v_{k}$ , gdzie $v_{0} = v_{k}$ . Dla cyklu tego mamy:

$\sum_{i = 0}^{k} w (v_{i}, v_{i + 1}) < 0 .$

      ((1))

Gdyby w tej sytuacji algorytm Bellmana-Forda zwrócił wartość TRUE to dla każdej krawędzi $(v_{i}, v_{i + 1})$ musiałaby zachodzić nierówność $d (v_{i}) + w (v_{i}, v_{i + 1}) \geq d (v_{i + 1})$ . Sumując tą nierówność stronami po wszystkich $i = 0, \dots, k - 1$ otrzymujemy.

\sum_{i = 0}^{k - 1} [d (v_{i}) + w (v_{i}, v_{i + 1})] \geq \sum_{i = 0}^{k - 1} d (v_{i + 1}),

\sum_{i = 0}^{k - 1} d (v_{i}) + \sum_{i = 0}^{k - 1} w (v_{i}, v_{i + 1}) \geq \sum_{i = 1}^{k} d (v_{i}),

ponieważ $v_{0} = v_{k}$ to

\sum_{i = 0}^{k - 1} d (v_{i}) + \sum_{i = 0}^{k - 1} w (v_{i}, v_{i + 1}) \geq \sum_{i = 0}^{k - 1} d (v_{i}) .

Wiemy, że cykl $c$ jest osiągalny a zatem dla każdego $i = 0, \dots, k$ mamy $d (v) < \infty$ . Możemy więc skrócić $\sum_{i = 0}^{k - 1} d (v_{i})$ po obydwu stronach równania i otrzymujemy:

\sum_{i = 0}^{k - 1} w (v_{i}, v_{i + 1}) \geq 0,

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

s

, to algorytm zwróci FALSE.

Mnożenie macierzy i najkrótsze ścieżki

@@ Linia 126: / Linia 126: @@
 }}
-{{dowod|||3=
+{{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.
-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.
-Zauważmy, że teza indukcyjna zachodzi po inicjacji algorytmu, gdyż
+Zauważmy, że teza indukcyjna zachodzi po inicjacji algorytmu, gdyż <math>d(v_0) = d(s) = 0 \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, 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>.
-<math>d(v_0) = d(s) = 0 \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, 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
+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ło by, z właściwości procedury [[#algorytm_relaksacja_krawędzi|RELAKSUJ]], że istnieje ścieżka od <math>s</math> do <math>v</math>. Sprzeczność.
-<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ło by, z właściwości procedury RELAKS,
-że istnieje ścieżka od <math>s</math> do <math>v</math>. Sprzeczność.
 }}
 {{dowod|||
-Dowód ten można przeprowadzić w podobny sposób do dowodu lematu
+Dowód ten można przeprowadzić w podobny sposób do dowodu lematu [[#poprawnosc_1|Lematu 1]].
-[[#poprawnosc_1|Lematu 1]].
 }}
 {{twierdzenie|3|bf_poprawnosc|3=
-Niech <math>G = (V,E)</math> będzie
+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 nie zawiera cyklu o ujemnej wadze osiągalnego ze źródła <math>s</math> to algorytm zwraca wartość TRUE, <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>. Jeżeli natomiast <math>G</math> zawiera cykl o ujemnej wadze osiągalny ze źródła to algorytm zwraca wartość FALSE.
-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 nie zawiera
-cyklu o ujemnej wadze osiągalnego ze źródła <math>s</math> to
-algorytm zwraca wartość TRUE, <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>. Jeżeli
-natomiast <math>G</math> zawiera cykl o ujemnej wadze osiągalny ze
-źródła to algorytm zwraca wartość FALSE.
 }}
-{{dowod|||3=Załóżmy najpierw, że graf nie zawiera cykli o ujemnej
+{{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 [[#poprawność_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]] relaks, która wyliczając odległość wyznaczą jednocześnie przez jaki wierzchołek  prowadzi ta najkrótsza ścieżka.
-wadze, które byłyby osiągalne z <math>s</math>. Wtedy z
-[[#poprawność_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ę RELAKS]] to <math>\pi(v)</math> koduje najkrótsze ścieżki w
-grafie. Wynika to z właściwości [[algorytm_relaksacja_krawędzi|
-funkcji RELAKS]] relaks, 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
+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:
-<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 206: / Linia 153: @@
-Powyższa nierówność zachodzi ponieważ <math>s \rightsquigarrow u
+Powyższa nierówność zachodzi ponieważ <math>s \rightsquidarrow u \rightsquidarrow v</math> jest ścieżką w grafie, a więc jest nie krótsza niż najkrótsza ścieżka <math>s \rightdquidarrow v</math>. Widzimy więc, że w tym przypadku żaden z testów w linijce 6 algorytmu nie będzie spełniony i algorytm zwróci TRUE.
-\rightsquigarrow v</math> jest ścieżką w grafie, a więc jest nie
-krótsza niż najkrótsza ścieżka <math>s \rightdquidarrow v</math>.
-Widzimy więc, że w tym przypadku żaden z testów w linijce 6 algorytmu
-nie będzie spełniony i algorytm zwróci TRUE.
-Załóżmy teraz, że w grafie <math>G</math> istnieje cykl  o ujemnej
+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:
-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)|
@@ Linia 223: / Linia 163: @@
 }}
-Gdyby w tej sytuacji algorytm Bellmana-Forda zwrócił wartość TRUE to
+Gdyby w tej sytuacji algorytm Bellmana-Forda zwrócił wartość TRUE 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.
-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 247: / Linia 183: @@
-Wiemy, że cykl <math>c</math> jest osiągalny a zatem dla każdego
+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:
-<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:
@@ Linia 258: / Linia 191: @@
-co stoi w sprzeczności z [[#wzor_cykl|nierównością (1)]]. Jeżeli więc w grafie
+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 FALSE.
-istnieje cykl o ujemnej wadze osiągalny z <math>s</math>, to algorytm zwróci FALSE.
 }}
 == Mnożenie macierzy i najkrótsze ścieżki ==

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

Wersja z 17:35, 20 lip 2006

Spis treści

Abstrakt

Definicja problemu

Algorytm Bellmana-Forda

Relaksacja

Algorytm

Mnożenie macierzy i najkrótsze ścieżki

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia