Fordbellman

Algorytm Forda-Bellmana to algorytm grafowy. Służy do wyznaczania najkrótszych
ścieżek i ich wag w grafie G z krawędziami o ujemnych wagach ze źródła s. W wypadku gdy w grafie
znajduje się ujemny cykl algorytm zatrzymuje się i informuje, że najktószych ścieżek nie da sie obliczyć.

Używa on tablicy d[V] i p[V]. Tablica d[V] zawiera wagi najkrótszych ścieżek dla kolejnych wierzchołków. Tablica p[V] pamięta dla każdego wierzchołka jego poprzednika na najkrótszej ścieżce.

Na początek wagę najkrótszej ścieżki dla źródła należy ustawić na 0, wagi pozostałych najkrótszych ścieżek na nieskończoność, a poprzednika wszystkich wierzchołków na nieznanego.

bool Ford-Bellman(G, d[],p[], s)
{
    dla każdego wierzchołka v należącego do V[G]
        d[v] = nieskończoność
        p[v] = nieznany
    d[s] = 0

    dla i = 1 do |V[G]| -1
        dla każdej krawędzi(u, v) należącej do E[V]
            RELAX(u, v)

    dla każdej krawędzi(u, v) należącej do E[V]
        jesli d[v]>d[u] + waga(d, v)
            zwróć fałsz
    zwróć prawda
}

Algorytm Forda-Bellmana opiera swe działanie na operacji relaksacji.
Relaksacja to inaczej osłabianie ograniczeń.

Relaksacja wykonana na krawędzi (u, v)
(krawędzi prowadzącej z wierzchołka u do wierzchołka v) sprawdza,
czy długość ścieżki prowadzącej do v przez wierzchołek u jest krótsza
od dotychczasowo najkrótszej scieżki pamiętanej przez tablicę d[V] dla wierzchołka v. Jeżeli
tak jest, zmniejsza starą wagę najkrótszej scieżki na nową, krótsza, przechodzącą przez krawędź (u, v).

W dużym skrócie algorytm to relaksacja przez wszystkie krawędzie powtórzona o jeden mniej razy niż ilość wierzchołków w grafie. Stąd też dość oczywiście wynika złożoność algorytmu: O(E*V)

void RELAX(u, v)
{
    jesli (d[v] > d[u] + waga(d, v))
        d[v] = d[u] + waga(d, v)
        p[v] = u
}

Relaksacja jest jedynym sposobem skrócania ścieżek. Jest podstawowym narzędziem algorytmów wyznaczających najkrótsze ścieżki. Wszystkie poznane przez nas algorytmy służące do wyznaczania najkrótszych ścieżek używają relaksacji. Różnią się jedynie sposobem zastosowania tej operacji.

Ponieważ formalny dowód nie jest prosty postaram się tylko mniej więcej powiedzieć dlaczego to działa.
Najkrótsza ścieżka w grafie może składać się z maksymalnie tylu krawędzi, ile jest wierzchołków w grafie. Jest tak, dlatego ze gdyby najkrótsza ścieżka przechodziła 2 razy przez ten sam wierzchołek nie była by najkrótszą. Wynika z tego, że jeśli poprawimy wszystkie krawędzie tyle razy, z ilu krawędzi maksymalnie mogła by składać się najkrótsza ścieżka dla dowolnego wierzchołka, to wyznaczymy najkrótsze ścieżki dla wszystkich wierzchołków.

W ostatniej pętli algorytmu sprawdzamy, czy relaksacja przez którąkolwiek z krawędzi nie skróci którejś z najkrótszych ścieżek. Jeśli tak się stanie, oznacza to , ze w grafie znajduje się co najmniej jeden cykl ujemny. Cykl ujemny ma to do siebie, że relaksację najkrótszej ścieżki przechodzącej przez jego krawędzie można wykonywać w nieskończoność zawsze skracając ową ścieżkę. Po zrelaksowaniu wszystkich krawędzi tyle razy ile jest wierzchołków dalsza relaksacja nie powinna dać efektów, gdyż najdłuższa ścieżka nie będąca cyklem ujemnym może mieć długość maksymalnie |V[G]|-1 (czyli o jeden mniej niż liczba wierzchołków w grafie)

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License