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


Сложный уровень средний
Часто спрашивают в Facebook Qualtrics
Динамическое программирование График Кратчайший путь

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

Теперь читатель может сказать:

У нас есть Дейкстра уже. Зачем заморачиваться с другим алгоритмом? Позвольте мне удовлетворить такие запросы с помощью недостатки Дейкстры

  • Это жадно!
  • Он не может работать с отрицательными весами
  • Таким образом, он может дать или не дать правильный ответ.

Таким образом, в этой статье мы стремимся охватить:

  • Как работает алгоритм Беллмана Форда?
  • Недостатки алгоритма Беллмана-Форда.

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

Для n вершин мы ослабляем ребра n-1 раз, где n - количество ребер. Давайте теперь посмотрим на уравнение релаксации который это самое главное в этом алгоритме.

Расслабьтесь (u, v):

если расстояние (v)> расстояние (u) + стоимость (u, v):

расстояние (v) = расстояние (u) + стоимость (u, v)

Где u и v ребра.

Теперь, когда мы знаем уравнение релаксации, давайте пройдемся по алгоритму шаг за шагом:

  • Инициализируйте расстояние от источника до места назначения как бесконечность.
  • Выберите любые два ребра и составьте список ребер.
  • Расслабляйте края до тех пор, пока кратчайшее расстояние не начнет повторяться, или, в худшем случае, n-1 раз.

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

Давайте лучше разберемся в этом на примере. На графике ниже источник = 0, количество вершин = 5

Изначально присваиваем все расстояния бесконечности и составляем список ребер

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

Ослабляя для (0,1), мы получаем 0 + 2 <∞, заставляя нас обновлять значение 1 как 2. Мы аналогичным образом расслабляем все края.

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

Это будет график, полученный после первой итерации.

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

Мы аналогичным образом обработаем график 5 раз, чтобы получить окончательный график с наименьшими расстояниями, полученными, как показано на графике ниже.

Теперь, когда мы поняли, как работает алгоритм, давайте реализуем его с помощью кода

Программа на Java для алгоритма Беллмана-Форда

import java.util.*;
class bellman
{
  public static void bell(int graph[][],int V,int E,int src)
  {
    int []distance=new int[V];
    //Initializing the distance to 1 for all the vertices
    for(int i=1;i<V;i++)
      distance[i]=Integer.MAX_VALUE;
    //Relaxing all the edges V-1 times
    for(int i=0;i<V;i++)
    {
      for(int j=0;j<E;j++)
      {      //dist(v)+cost(u,v)<dist(v)
        if(distance[graph[j][0]]+graph[j][2]<distance[graph[j][1]])
        {
          distance[graph[j][1]]=distance[graph[j][0]]+graph[j][2];
        }
      }
    }
    //Checking for negative weight cycle
    for(int i=0;i<E;i++)
    {
      int start=graph[i][0];
      int desti=graph[i][1];
      int cost=graph[i][2];
      if(distance[start]!=Integer.MAX_VALUE && distance[start]+cost<distance[desti])
        System.out.println("Negative weight cycle detected");
    }
    for(int i=0;i<V;i++)
    {
      System.out.println("Shortest distance from 0 to:"+i+" is "+distance[i]);
    }
    
  }
  public static void main(String args[])
  {
    int V=5;
    int E=7;
    int graph[][]={{0,1,2},{0,3,1},{0,2,6},
    {1,3,3},{1,4,6},
    {2,4,1},
    {3,4,5}};
    bell(graph,V,E,0);
  } 
}

Код C ++

#include <bits/stdc++.h> 
struct Edge 
{ 
    int src, dest, weight; 
}; 

struct Graph 
{ 
    int V, E; 
    struct Edge* edge; 
}; 

struct Graph* create(int V, int E) 
{ 
    struct Graph* graph = new Graph; 
    graph->V = V; 
    graph->E = E; 
    graph->edge = new Edge[E]; 
    return graph; 
} 
void chkres(int dist[], int n) 
{ 
    printf("Vertex   Distance from\n"); 
    for (int i = 0; i < n; ++i) 
        printf("%d \t %d\n", i, dist[i]); 
} 
  
void BellmanFord(struct Graph* graph, int src) 
{ 
    int V = graph->V; 
    int E = graph->E; 
    int dist[V]; 
    //Initalizing to infinity
    for (int i = 0; i < V; i++) 
        dist[i] = INT_MAX; 
    dist[src] = 0; 
  
    //Relaxing all edges |V| - 1 times.
    for (int i = 1; i <= V - 1; i++) { 
        for (int j = 0; j < E; j++) { 
            int u = graph->edge[j].src; 
            int v = graph->edge[j].dest; 
            int weight = graph->edge[j].weight; 
            if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) 
                dist[v] = dist[u] + weight; 
        } 
    }  
    for (int i = 0; i < E; i++) 
    { 
        int u = graph->edge[i].src; 
        int v = graph->edge[i].dest; 
        int weight = graph->edge[i].weight; 
        if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
        { 
            printf("Graph contains negative weight cycle");
            return;
        } 
    } 
    chkres(dist, V); 
    return; 
} 
  
int main() 
{
    int V = 4; 
    int E = 4;
    struct Graph* graph = create(V, E); 
    graph->edge[0].src = 0; 
    graph->edge[0].dest = 1; 
    graph->edge[0].weight = 3; 
    graph->edge[1].src = 0; 
    graph->edge[1].dest = 2; 
    graph->edge[1].weight = -2;
    graph->edge[2].src = 1; 
    graph->edge[2].dest = 2; 
    graph->edge[2].weight = 1; 
    graph->edge[3].src = 1; 
    graph->edge[3].dest = 3; 
    graph->edge[3].weight = 0; 
    BellmanFord(graph, 0); 
  
    return 0; 
}
Vertex   Distance from
0 	 0
1 	 3
2 	 -2
3 	 3

Анализ сложности

Временная сложность этого алгоритма в сумме составляет O (V * E), где V - количество вершин, а E - количество ребер в график.

Преимущества и приложения в реальной жизни 

  • Также работает с отрицательными весами. Это может сработать там, где в некоторых случаях мы можем получить некоторое преимущество, выбрав определенный путь. Пример. Во время поездки на матч по крикету могут быть некоторые дороги, по которым нам, возможно, придется платить налоги, и некоторые пути, где находятся дома наших родственников, которые могут дать немного денег или подарков, если мы зайдем к их дому.
  • Хорошо работает для распределенных систем
  • Это динамический алгоритм

Недостатки алгоритма Беллмана-Форда

  • Это может работать только для ориентированных графов
  • Требуется только местная информация

дело