Алгоритам Беллман Форд нам помаже да пронађемо најкраћи пут од темена до свих осталих темена пондерисаног графа.
Сличан је Дијкстрином алгоритму, али може да ради са графиконима на којима ивице могу имати негативне тежине.
Зашто би ико у животу имао ивице са негативном тежином?
Ивице негативне тежине у почетку могу изгледати бескорисно, али могу објаснити многе појаве попут новчаног тока, топлоте која се ослобађа / апсорбује у хемијској реакцији итд.
На пример, ако постоје различити начини да се дође од једне хемикалије А до друге хемикалије Б, свака метода ће имати подреакције које укључују и расипање и апсорпцију топлоте.
Ако желимо да пронађемо скуп реакција где је потребна минимална енергија, тада ћемо бити у стању да фактор апсорпције топлоте рачунамо као негативне тежине и одвођење топлоте као позитивне тежине.
Зашто треба бити опрезан са негативним теговима?
Ивице негативне тежине могу створити циклусе негативне тежине, тј. Циклус који ће смањити укупну удаљеност пута враћајући се у исту тачку.
Негативни циклуси тежине могу дати нетачан резултат када се покушава пронаћи најкраћи пут
Најкраћи алгоритми путање попут Дијкстриног алгоритма који нису у стању да открију такав циклус могу дати нетачан резултат јер могу проћи кроз циклус негативне тежине и смањити дужину путање.
Како функционише алгоритам Беллман Форд
Алгоритам Беллман Форд делује тако што прецењује дужину путање од почетног темена до свих осталих темена. Тада итеративно ублажава те процене проналажењем нових путева који су краћи од претходно прецењених путева.
Радећи ово више пута за све темене, можемо гарантовати да је резултат оптимизован.
Корак-1 за алгоритам Беллман Форд 
Корак-2 за алгоритам Беллман Форд 
Корак-3 за алгоритам Беллман Форд 
Корак-4 за алгоритам Беллман Форд 
Корак-5 за алгоритам Беллман Форд 
Корак-6 за алгоритам Беллман Форд
Беллман Форд Псеудоцоде
Морамо одржавати путну раздаљину сваког темена. То можемо похранити у низ величине в, где је в број врхова.
Такође желимо да можемо да стигнемо најкраћим путем, не само да знамо дужину најкраћег пута. Због тога мапирамо сваки врх на врх који је последњи пут ажурирао дужину путање.
Када се алгоритам заврши, можемо се вратити из одредишног темена у изворни врх да бисмо пронашли путању.
функција беллманФорд (Г, С) за сваки врх В у раздаљини Г (В) <- бесконачно претходно (В) <- НУЛЛ растојање (С) <- 0 за сваки врх В у Г за сваку ивицу (У, В) у Г темпДистанце <- дистанце (У) + едге_веигхт (У, В) иф темпДистанце <дистанце (В) дистанце (В) <- темпДистанце превиоус (В) <- У фор еацх едге (У, В) ин Г Иф дистанце (У) + едге_веигхт (У, В) <дистанце (В) Грешка: Негативни циклус постоји повратна удаљеност (), претходна ()
Белман Форд вс Дијкстра
Алгоритам Беллман Форд и Дијкстра су врло слични у структури. Док Дијкстра гледа само на непосредне суседе темена, Белман пролази кроз сваку ивицу у свакој итерацији.
Дијкстра-ин вс Беллман Форд-ов алгоритам
Примери за Питхон, Јава и Ц / Ц ++
Питхон Јава Ц Ц ++ # Bellman Ford Algorithm in Python class Graph: def __init__(self, vertices): self.V = vertices # Total number of vertices in the graph self.graph = () # Array of edges # Add edges def add_edge(self, s, d, w): self.graph.append((s, d, w)) # Print the solution def print_solution(self, dist): print("Vertex Distance from Source") for i in range(self.V): print("(0) (1)".format(i, dist(i))) def bellman_ford(self, src): # Step 1: fill the distance array and predecessor array dist = (float("Inf")) * self.V # Mark the source vertex dist(src) = 0 # Step 2: relax edges |V| - 1 times for _ in range(self.V - 1): for s, d, w in self.graph: if dist(s) != float("Inf") and dist(s) + w < dist(d): dist(d) = dist(s) + w # Step 3: detect negative cycle # if value changes then we have a negative cycle in the graph # and we cannot find the shortest distances for s, d, w in self.graph: if dist(s) != float("Inf") and dist(s) + w < dist(d): print("Graph contains negative weight cycle") return # No negative weight cycle found! # Print the distance and predecessor array self.print_solution(dist) g = Graph(5) g.add_edge(0, 1, 5) g.add_edge(0, 2, 4) g.add_edge(1, 3, 3) g.add_edge(2, 1, 6) g.add_edge(3, 2, 2) g.bellman_ford(0)
// Bellman Ford Algorithm in Java class CreateGraph ( // CreateGraph - it consists of edges class CreateEdge ( int s, d, w; CreateEdge() ( s = d = w = 0; ) ); int V, E; CreateEdge edge(); // Creates a graph with V vertices and E edges CreateGraph(int v, int e) ( V = v; E = e; edge = new CreateEdge(e); for (int i = 0; i < e; ++i) edge(i) = new CreateEdge(); ) void BellmanFord(CreateGraph graph, int s) ( int V = graph.V, E = graph.E; int dist() = new int(V); // Step 1: fill the distance array and predecessor array for (int i = 0; i < V; ++i) dist(i) = Integer.MAX_VALUE; // Mark the source vertex dist(s) = 0; // Step 2: relax edges |V| - 1 times for (int i = 1; i < V; ++i) ( for (int j = 0; j < E; ++j) ( // Get the edge data int u = graph.edge(j).s; int v = graph.edge(j).d; int w = graph.edge(j).w; if (dist(u) != Integer.MAX_VALUE && dist(u) + w < dist(v)) dist(v) = dist(u) + w; ) ) // Step 3: detect negative cycle // if value changes then we have a negative cycle in the graph // and we cannot find the shortest distances for (int j = 0; j < E; ++j) ( int u = graph.edge(j).s; int v = graph.edge(j).d; int w = graph.edge(j).w; if (dist(u) != Integer.MAX_VALUE && dist(u) + w < dist(v)) ( System.out.println("CreateGraph contains negative w cycle"); return; ) ) // No negative w cycle found! // Print the distance and predecessor array printSolution(dist, V); ) // Print the solution void printSolution(int dist(), int V) ( System.out.println("Vertex Distance from Source"); for (int i = 0; i 1 graph.edge(0).s = 0; graph.edge(0).d = 1; graph.edge(0).w = 5; // edge 0 --> 2 graph.edge(1).s = 0; graph.edge(1).d = 2; graph.edge(1).w = 4; // edge 1 --> 3 graph.edge(2).s = 1; graph.edge(2).d = 3; graph.edge(2).w = 3; // edge 2 --> 1 graph.edge(3).s = 2; graph.edge(3).d = 1; graph.edge(3).w = 6; // edge 3 --> 2 graph.edge(4).s = 3; graph.edge(4).d = 2; graph.edge(4).w = 2; graph.BellmanFord(graph, 0); // 0 is the source vertex ) )
// Bellman Ford Algorithm in C #include #include #define INFINITY 99999 //struct for the edges of the graph struct Edge ( int u; //start vertex of the edge int v; //end vertex of the edge int w; //weight of the edge (u,v) ); //Graph - it consists of edges struct Graph ( int V; //total number of vertices in the graph int E; //total number of edges in the graph struct Edge *edge; //array of edges ); void bellmanford(struct Graph *g, int source); void display(int arr(), int size); int main(void) ( //create graph struct Graph *g = (struct Graph *)malloc(sizeof(struct Graph)); g->V = 4; //total vertices g->E = 5; //total edges //array of edges for graph g->edge = (struct Edge *)malloc(g->E * sizeof(struct Edge)); //------- adding the edges of the graph /* edge(u, v) where u = start vertex of the edge (u,v) v = end vertex of the edge (u,v) w is the weight of the edge (u,v) */ //edge 0 --> 1 g->edge(0).u = 0; g->edge(0).v = 1; g->edge(0).w = 5; //edge 0 --> 2 g->edge(1).u = 0; g->edge(1).v = 2; g->edge(1).w = 4; //edge 1 --> 3 g->edge(2).u = 1; g->edge(2).v = 3; g->edge(2).w = 3; //edge 2 --> 1 g->edge(3).u = 2; g->edge(3).v = 1; g->edge(3).w = 6; //edge 3 --> 2 g->edge(4).u = 3; g->edge(4).v = 2; g->edge(4).w = 2; bellmanford(g, 0); //0 is the source vertex return 0; ) void bellmanford(struct Graph *g, int source) ( //variables int i, j, u, v, w; //total vertex in the graph g int tV = g->V; //total edge in the graph g int tE = g->E; //distance array //size equal to the number of vertices of the graph g int d(tV); //predecessor array //size equal to the number of vertices of the graph g int p(tV); //step 1: fill the distance array and predecessor array for (i = 0; i < tV; i++) ( d(i) = INFINITY; p(i) = 0; ) //mark the source vertex d(source) = 0; //step 2: relax edges |V| - 1 times for (i = 1; i <= tV - 1; i++) ( for (j = 0; j edge(j).u; v = g->edge(j).v; w = g->edge(j).w; if (d(u) != INFINITY && d(v)> d(u) + w) ( d(v) = d(u) + w; p(v) = u; ) ) ) //step 3: detect negative cycle //if value changes then we have a negative cycle in the graph //and we cannot find the shortest distances for (i = 0; i edge(i).u; v = g->edge(i).v; w = g->edge(i).w; if (d(u) != INFINITY && d(v)> d(u) + w) ( printf("Negative weight cycle detected!"); return; ) ) //No negative weight cycle found! //print the distance and predecessor array printf("Distance array: "); display(d, tV); printf("Predecessor array: "); display(p, tV); ) void display(int arr(), int size) ( int i; for (i = 0; i < size; i++) ( printf("%d ", arr(i)); ) printf(""); )
// Bellman Ford Algorithm in C++ #include // Struct for the edges of the graph struct Edge ( int u; //start vertex of the edge int v; //end vertex of the edge int w; //w of the edge (u,v) ); // Graph - it consists of edges struct Graph ( int V; // Total number of vertices in the graph int E; // Total number of edges in the graph struct Edge* edge; // Array of edges ); // Creates a graph with V vertices and E edges struct Graph* createGraph(int V, int E) ( struct Graph* graph = new Graph; graph->V = V; // Total Vertices graph->E = E; // Total edges // Array of edges for graph graph->edge = new Edge(E); return graph; ) // Printing the solution void printArr(int arr(), int size) ( int i; for (i = 0; i V; int E = graph->E; int dist(V); // Step 1: fill the distance array and predecessor array for (int i = 0; i < V; i++) dist(i) = INT_MAX; // Mark the source vertex dist(u) = 0; // Step 2: relax edges |V| - 1 times for (int i = 1; i <= V - 1; i++) ( for (int j = 0; j edge(j).u; int v = graph->edge(j).v; int w = graph->edge(j).w; if (dist(u) != INT_MAX && dist(u) + w < dist(v)) dist(v) = dist(u) + w; ) ) // Step 3: detect negative cycle // if value changes then we have a negative cycle in the graph // and we cannot find the shortest distances for (int i = 0; i edge(i).u; int v = graph->edge(i).v; int w = graph->edge(i).w; if (dist(u) != INT_MAX && dist(u) + w 1 graph->edge(0).u = 0; graph->edge(0).v = 1; graph->edge(0).w = 5; //edge 0 --> 2 graph->edge(1).u = 0; graph->edge(1).v = 2; graph->edge(1).w = 4; //edge 1 --> 3 graph->edge(2).u = 1; graph->edge(2).v = 3; graph->edge(2).w = 3; //edge 2 --> 1 graph->edge(3).u = 2; graph->edge(3).v = 1; graph->edge(3).w = 6; //edge 3 --> 2 graph->edge(4).u = 3; graph->edge(4).v = 2; graph->edge(4).w = 2; BellmanFord(graph, 0); //0 is the source vertex return 0; )
Комплексност Беллмана Форда
Сложеност времена
| Најбољи случај сложености | О (Е) |
| Просечна сложеност предмета | О (ВЕ) |
| Најгори случај сложености | О (ВЕ) |
Сложеност простора
И, сложеност простора је O(V).
Примене алгоритма Беллман Форд
- За израчунавање најкраћих путања у алгоритмима рутирања
- За проналажење најкраћег пута
