Алгоритъмът на Белман Форд

Алгоритъмът на Белман Форд ни помага да намерим най-краткия път от върха до всички други върхове на претеглена графика.

Той е подобен на алгоритъма на Дейкстра, но може да работи с графики, в които ръбовете могат да имат отрицателни тегла.

Защо някой в ​​реалния живот някога да има ръбове с отрицателни тегла?

Отрицателните ръбове на теглото може да изглеждат безполезни в началото, но те могат да обяснят много явления като паричен поток, отделената / погълната топлина при химическа реакция и т.н.

Например, ако има различни начини за достигане от един химикал А до друг химикал В, всеки метод ще има подреакции, включващи както разсейване, така и поглъщане на топлина.

Ако искаме да намерим набора от реакции, при които се изисква минимална енергия, тогава ще трябва да можем да вземем предвид абсорбцията на топлина като отрицателни тегла и разсейването на топлината като положителни тегла.

Защо трябва да внимаваме с отрицателните тегла?

Отрицателните ръбове на тежестта могат да създадат цикли с отрицателно тегло, т.е. цикъл, който ще намали общото разстояние на пътя, като се върне в същата точка.

Отрицателните цикли на тегло могат да дадат неправилен резултат, когато се опитвате да откриете най-краткия път

Най-късите алгоритми на пътя като алгоритъма на Дейкстра, които не са в състояние да открият такъв цикъл, могат да дадат неправилен резултат, тъй като могат да преминат през отрицателен цикъл на тежестта и да намалят дължината на пътя.

Как работи алгоритъмът на Белман Форд

Алгоритъмът на Белман Форд работи, като надценява дължината на пътя от началния връх до всички други върхове. След това итеративно облекчава тези оценки, като намира нови пътища, които са по-кратки от преди това надценените пътища.

Правейки това многократно за всички върхове, можем да гарантираме, че резултатът е оптимизиран.

Стъпка-1 за алгоритъма на Bellman Ford Стъпка-2 за алгоритъма на Bellman Ford Стъпка-3 за алгоритъма на Bellman Ford Стъпка-4 за алгоритъма на Bellman Ford Стъпка-5 за алгоритъма на Bellman Ford Стъпка-6 за алгоритъма на Bellman Ford

Bellman Ford Pseudocode

Трябва да поддържаме разстоянието на пътя на всеки връх. Можем да съхраним това в масив с размер v, където v е броят на върховете.

Ние също искаме да можем да получим най-краткия път, не само да знаем дължината на най-краткия път. За това ние връзваме всеки връх към върха, който последно е обновил дължината на пътя си.

След като алгоритъмът приключи, можем да се върнем от върха на дестинацията към върха на източника, за да намерим пътя.

 функция bellmanFord (G, S) за всеки връх V в G разстояние (V) <- безкрайно предишно (V) <- NULL разстояние (S) <- 0 за всеки връх V в G за всеки ръб (U, V) в G tempDistance <- разстояние (U) + тегло_ край (U, V), ако tempDistance <разстояние (V) разстояние (V) <- tempDistance предишно (V) <- U за всеки ръб (U, V) в G Ако разстояние (U) + edge_weight (U, V) <разстояние (V) Грешка: Отрицателен цикъл Съществува връщане на разстояние (), предишен ()

Белман Форд срещу Дейкстра

Алгоритъмът на Белман Форд и алгоритъмът на Дейкстра са много сходни по структура. Докато Дейкстра гледа само на непосредствените съседи на даден връх, Белман преминава през всеки ръб във всяка итерация.

Алгоритъмът на Дейкстра срещу Белман Форд

Примери за Python, Java и C / C ++

Python Java C C ++ 
 # 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 (E)
Средна сложност на случая O (VE)
Сложност на най-лошия случай O (VE)

Сложност на пространството

И космическата сложност е O(V).

Алгоритъм на приложенията на Белман Форд

  1. За изчисляване на най-кратките пътища в алгоритмите за маршрутизиране
  2. За намиране на най-краткия път

Интересни статии...