Bellman Ford Algorithm Dawid - MarcinG121/INPGProject GitHub Wiki

  1. Wprowadzenie

Algorytm Bellmana-Forda służy do znajdowania najktrótszej drogi z wierzchołka s w grafie skierowanym bez cykli o ujemnej długości. Algorytm ten bazuje na na metodzie relaksacji, zmniejszając stopniowo oszacowanie d[v] na wagę najkrótszej ścieżki ze źródła s do każdego wierzchołka, aż zostanie osiągnięta rzeczewista waga najkrótszej drogi. Algorytm zwraca TRUE jeśli graf nie zawiera cykli ujemnych wagach osiągalnych ze źródła.

  1. Działanie

Po wykonaniu inicjacji algorytm przetwarza krawędzie grafu w V - 1 przebiegach. Każdy przebieg jest jedną iteracją pętli for i polega na jednarazowej relaksacji każdej krawędzi. Po wykonaniu wszystkich V - 1 przebiegów sprawdza się, czy istnieje cykl o ujemnej wadze, i zwraca właściwą wartość logiczną.

  1. Złożoność obliczeniowa: O(V*E) Złoźoność pamięciowa: O(V)

  2. Przykładowy pseudokod:

function BellmanFord(list vertices, list edges, vertex source) ::distance[],predecessor[]

// Step 1: initialize graph for each vertex v in vertices: distance[v] := inf
predecessor[v] := null

distance[source] := 0

// Step 2: relax edges repeatedly for i from 1 to size(vertices)-1: for each edge (u, v) with weight w in edges: if distance[u] + w < distance[v]: distance[v] := distance[u] + w predecessor[v] := u

// Step 3: check for negative-weight cycles for each edge (u, v) with weight w in edges: if distance[u] + w < distance[v]: error "Graph contains a negative-weight cycle"

return distance[], predecessor[]

  1. Bibliografia i więcej informacji: