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

Алгоритм Беллмана Форда допомагає нам знайти найкоротший шлях від вершини до всіх інших вершин зваженого графа.

Це схоже на алгоритм Дейкстри, але він може працювати з графіками, в яких ребра можуть мати від’ємні ваги.

Чому в реальному житті хтось мав краї з негативними вагами?

Спочатку негативні краї ваги можуть здатися марними, але вони можуть пояснити багато явищ, таких як грошовий потік, тепло, що виділяється / поглинається в результаті хімічної реакції тощо.

Наприклад, якщо існують різні способи переходу від однієї хімічної речовини А до іншої хімічної речовини В, кожен метод матиме субреакції, що включають як розсіювання, так і поглинання тепла.

Якщо ми хочемо знайти набір реакцій, де потрібна мінімальна енергія, тоді нам потрібно мати змогу врахувати поглинання тепла як негативні ваги, а тепловиділення як позитивні ваги.

Чому нам потрібно бути обережними з негативними вагами?

Негативні ребра ваги можуть створювати негативні вагові цикли, тобто цикл, який зменшить загальну відстань шляху, повернувшись до тієї самої точки.

Негативні цикли ваги можуть дати неправильний результат при спробі з’ясувати найкоротший шлях

Найкоротші алгоритми шляху, такі як Алгоритм Дейкстри, які не здатні виявити такий цикл, можуть дати неправильний результат, оскільки вони можуть пройти цикл негативної ваги та зменшити довжину шляху.

Як працює алгоритм Беллмана Форда

Алгоритм Беллмана Форда працює, завищуючи довжину шляху від початкової вершини до всіх інших вершин. Потім він ітеративно послаблює ці оцінки, знаходячи нові шляхи, які є коротшими, ніж раніше завищені шляхи.

Повторюючи це для всіх вершин, ми можемо гарантувати оптимізацію результату.

Крок-1 для алгоритму Беллмана Форда Крок-2 для алгоритму Беллмана Форда Крок-3 для алгоритму Беллмана Форда Крок-4 для алгоритму Беллмана Форда Крок-5 для алгоритму Беллмана Форда Крок-6 для алгоритму Беллмана Форда

Беллман Форд Псевдокод

Нам потрібно підтримувати відстань шляху до кожної вершини. Ми можемо зберегти це в масиві розміром v, де v - кількість вершин.

Ми також хочемо мати найкоротший шлях, а не тільки знати довжину найкоротшого шляху. Для цього ми зіставляємо кожну вершину з вершиною, яка востаннє оновила довжину шляху.

Після того, як алгоритм закінчиться, ми можемо повернутися до вершини призначення до вершини джерела, щоб знайти шлях.

 функція bellmanFord (G, S) для кожної вершини V у відстані G (V) <- нескінченна попередня (V) <- НУЛЬ відстань (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. Для пошуку найкоротшого шляху

Цікаві статті...