Algorytm Bellmana-Forda

03.10.2010 - Damian Rusak
TrudnośćTrudność

Optymalne ścieżki

Zastanówmy się chwilę nad tym, jak wyglądają najkrótsze ścieżki w grafie. Jeżeli pytalibyśmy nie tylko o najtańsze połączenie między dwoma wybranymi wierzchołkami, ale starali się znaleźć najtańsze połączenie między pewnym wierzchołkiem startowym, a wszystkimi pozostałymi, to szybko zauważymy, że:

Jeżeli najtańsza ścieżka do wierzchołka $ E $ prowadzi przez wierzchołek $ B $, to początek tej ścieżki, wiodący do $ B $ musi być najtańszą ścieżką do $ B $.

Innymi słowy - najtańsze ścieżki korzystają z krótszych najtańszych ścieżek - gdyby do wspomnianego wierzchołka $ B $ dało się dojść taniej, niż zostało to wykorzystane przy przejściu do $ E $, to ścieżka nie byłaby optymalna - można by poprawić przejście do $ B $ a potem "dołożyć" pozostałe krawędzie aż do $ $ $.

Jeśli ścieżka $ x $ jest droższa niż optymalna ścieżka $ y $ z $ A $ do $ B $, to ścieżka z $ A $ do $ E $ prowadząca przez $ x $ i $ z $ nie może być optymalna. Musi zawierać optymalne połączenie między $ A $ i $ B $.

Pozostaje nam jeszcze jedna obserwacja, aby zbliżyć się do algorytmu. Poprzedni pomysł związany z optymalnymi ścieżkami daje nam jedną szczególną własność - jeśli chcemy znaleźć najkrótszą ścieżkę do pewnego wierzchołka, to jakoś ta ścieżka musiała doń "wejść" - musi ona przychodzić od jakiegoś sąsiada. Wobec tego możemy spojrzeć na całą tę sprawę bardziej lokalnie, jak na "podłączanie" się wierzchołków do krótszych ścieżek.

Nasze podejście będzie polegało na stopniowym znajdowaniu coraz lepszych ścieżek dochodzących do wszystkich wierzchołków.

Poprawianie wyników

Jeśli udało nam się znaleźć dobry sposób na dojście do pewnego wierzchołka, to za pomocą tego rozwiązania możemy poprawić rozwiązania dla jego sąsiadów. Jeżeli do wierzchołka $ A $ możemy dojść kosztem $ x $ i wierzchołek $ A $ jest połączony z wierzchołkiem $ B $ krawędzią o koszcie $ c $, to możemy zaproponować dla wierzchołka $ B $ koszt dojścia równy $ x+c $ - można wszak poprowadzić ścieżkę do $ B $ wiodącą przez $ A $ i łączącą ich krawędź.

Taką operację będziemy nazywali relaksacją krawędzi

Spójrz na animację poniżej - pokazuje ona jak kolejno można poprawiać odległości do wszystkich wierzchołków. Na początku wszystkie wierzchołki (poza startem, który ma odległość $ 0 $) mają odległość ustawioną na $ \infty $ - symbol nieskończoności, oznaczający, że dany wierzchołek jeszcze nie został ani razu odwiedzony. Na czerwono zaznaczane są krawędzie, które są relaksowane, czyli wykorzystane do poprawienia odległości dla wierzchołka, do którego krawędź wchodzi.

Relaksacja działa

Bardzo ważne jest to, że za pomocą relaksacji krawędzi można znaleźć najtańszą ścieżkę od startu do dowolnego innego wierzchołka (cały czas zakładamy, że nie ma w grafie cyklu ujemnego). Oznaczmy wierzchołek początkowy jako $ s $. Zauważ, że jeśli najtańsza ścieżka z $ s $ (długości $ k $) do pewnego wierzchołka $ v $ składa się z wierzchołków $ s $, $ w_{1} $, $ w_{2} $, ..., $ w_{k-1} $, $ v $, to wystarczy relaksować kolejno krawędzie $ (s, w_{1}) $, $ (w_{1}, w_{2}) $, ... , $ (w_{k-1}, v) $

Pierwsza relaksacja ustali najtańszą ścieżkę do $ w_{1} $ (pamiętasz, jak zaobserwowaliśmy, że dowolna część najtańszej ścieżki do $ v $ musi być też najtańszą ścieżką). Po drugiej relaksacji mamy już najtańszą ścieżkę do $ w_{2} $ i tak dalej aż do $ v $.

 

5
Twoja ocena: Brak Ocena: 5 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com