Bellman Ford 알고리즘


난이도 중급
자주 묻는 질문 페이스북 서비스 Qualtrics
동적 프로그래밍 그래프 최단 경로

Bellman Ford 암호알고리즘 소스 정점에서 모든 정점까지의 최단 경로를 찾는 데 사용됩니다. 음수 또는 양수일 수있는 간선의 가중치와 소스 정점이있는 그래프가 제공됩니다.

이제 독자는 다음과 같이 말할 수 있습니다.

우리는이 Dijkstra 이미. 왜 다른 알고리즘에 신경을 쓰나요? 이러한 쿼리를 Dijkstra의 단점

  • 욕심쟁이!
  • 음의 가중치로는 작동하지 않습니다.
  • 따라서 정답을 제공하거나 제공하지 않을 수 있습니다.

따라서이 기사에서는 다음 사항을 다룹니다.

  • Bellman Ford 알고리즘은 어떻게 작동합니까?
  • Bellman Ford 알고리즘의 단점.

Bellman Ford Algorithm은 어떻게 작동합니까?

n 개의 정점에 대해 n-1 번 가장자리를 완화합니다. 여기서 n은 가장자리의 수입니다. 이제 살펴 보겠습니다. 이완 방정식 어느 이 알고리즘에서 가장 중요한 것은.

휴식 (u, v) :

if distance (v)> distance (u) + cost (u, v) :

거리 (v) = 거리 (u) + 비용 (u, v)

여기서 u와 v는 모서리입니다.

이제 이완 방정식을 알았으므로 알고리즘을 단계별로 살펴 보겠습니다.

  • 소스에서 목적지까지의 거리를 무한대로 초기화합니다.
  • 두 가장자리를 선택하고 가장자리 목록을 만듭니다.
  • 최단 거리가 자체적으로 반복되거나 최악의 시나리오에서 n-1 회 반복되기 시작할 때까지 가장자리를 이완합니다.

Bellman Ford 알고리즘의 예

예를 들어 이것을 더 잘 이해합시다. 아래 그래프에서 source = 0, number of vertices = 5

처음에 모든 거리를 무한대로 할당하고 가장자리 목록을 만듭니다.

Bellman Ford 알고리즘

(0,1)에 대해 이완하면 0 + 2 <∞가 있으므로 1의 값을 2로 업데이트합니다. 마찬가지로 모든 가장자리를 이완합니다.

Bellman Ford 알고리즘

이것은 첫 번째 반복 후에 얻은 그래프입니다.

Bellman Ford 알고리즘

아래 그래프와 같이 최소 거리를 얻은 최종 그래프에 도달하기 위해 그래프를 5 번 유사하게 처리합니다.

알고리즘이 어떻게 작동하는지 이해 했으므로 이제 코드를 사용하여 구현할 수 있습니다.

Bellman Ford 알고리즘 용 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는 그래프.

장점 및 실제 응용 

  • 음의 가중치에도 적용됩니다. 이것은 경우에 따라 특정 경로를 택하여 이점을 얻을 수있는 곳에서 작동 할 수 있습니다. 예-크리켓 경기에가는 동안 세금을 내야하는 경로와 집에 들르면 돈이나 선물을 줄 수있는 친척의 집이있는 경로가있을 수 있습니다.
  • 분산 시스템에 적합
  • 그것은 동적 연산

Bellman Ford 알고리즘의 단점

  • 유 방향 그래프에서만 작동합니다.
  • 지역 정보 만 필요합니다.

참조