logo

TechCodeview

벨만-포드 알고리즘

여러 도시가 도로로 연결되어 있고 각 도로는 일정한 거리를 두고 있는 지도가 있다고 상상해 보세요. 그만큼 벨만-포드 알고리즘 일부 도로의 길이가 음수인 경우에도 한 도시에서 다른 모든 도시까지의 최단 경로를 찾는 데 도움이 되는 가이드와 같습니다. 그것은 마치 GPS 컴퓨터의 경우 네트워크의 한 지점에서 다른 지점으로 이동하는 가장 빠른 방법을 찾는 데 유용합니다. 이 글에서는 이 알고리즘이 어떻게 작동하는지, 그리고 일상적인 문제를 해결하는 데 왜 그토록 편리한지 자세히 살펴보겠습니다.

벨만-포드-알고리즘

내용의 테이블



벨만-포드 알고리즘

벨먼-포드 는 단일 소스 주어진 소스 정점과 그래프의 다른 모든 정점 사이의 최단 경로를 결정하는 최단 경로 알고리즘입니다. 이 알고리즘은 두 가지 모두에서 사용할 수 있습니다. 가중 그리고 비가중 그래프.

디렉토리 이름 바꾸기

ㅏ 벨먼-포드 알고리즘은 또한 다음과 유사하게 그래프에서 최단 경로를 찾는 것이 보장됩니다. Dijkstra의 알고리즘 . Bellman-Ford는 속도가 느리지만 Dijkstra의 알고리즘 , 그래프를 처리할 수 있습니다. 음수 간선 가중치 , 이는 더 다양한 기능을 제공합니다. 존재하는 경우 최단 경로를 찾을 수 없습니다. 네거티브 사이클 그래프에서. 계속해서 음의 사이클을 무한대로 돌면 경로 길이가 늘어나더라도 경로 비용은 계속해서 감소합니다. 결과적으로, 벨먼-포드 탐지도 가능하다 음의 순환 , 이는 중요한 기능입니다.

Bellman Ford 알고리즘의 기본 아이디어:

Bellman-Ford 알고리즘의 주요 원리는 단일 소스에서 시작하여 각 노드까지의 거리를 계산한다는 것입니다. 처음에는 거리는 알 수 없으며 무한하다고 가정하지만 시간이 지남에 따라 알고리즘은 몇 가지 더 짧은 경로를 식별하여 해당 경로를 완화합니다. 따라서 Bellman-Ford는 다음을 기반으로 한다고 합니다. 이완의 원리 .

Bellman-Ford의 모서리 완화 원리:

  • 그래프에 대해 다음과 같이 명시되어 있습니다. N 꼭짓점, 모든 가장자리는 완화되어야 합니다. N-1 단일 소스 최단 경로를 계산하는 데 걸리는 시간입니다.
  • 음의 순환이 존재하는지 여부를 감지하기 위해 모든 가장자리를 한 번 더 완화하고 임의의 노드에 대한 최단 거리가 감소하면 음의 순환이 존재한다고 말할 수 있습니다. 간단히 말해서 가장자리를 완화하면 N 번, 그리고 노드 사이의 모든 노드의 최단 거리에 변화가 있습니다. N-1번 그리고 N번째 부정적인 순환보다 완화가 존재하고, 그렇지 않으면 존재하지 않습니다.

Edges를 N-1번 완화하면 단일 소스 최단 경로가 제공되는 이유는 무엇입니까?

최악의 경우 두 정점 사이의 최단 경로는 최대 N-1 가장자리, 어디에 N 정점의 수입니다. 이는 그래프의 간단한 경로가 다음과 같기 때문입니다. N 정점은 최대 N-1 정점을 다시 방문하지 않고는 닫힌 루프를 형성하는 것이 불가능하기 때문입니다.

가장자리를 완화하여 N-1 Bellman-Ford 알고리즘은 그래프에 소스 정점에서 도달할 수 있는 음의 가중치 사이클이 포함되어 있지 않다는 가정하에 모든 정점에 대한 거리 추정치가 최적의 값으로 업데이트되었는지 확인합니다. 그래프에 소스 정점에서 도달할 수 있는 음의 가중치 사이클이 포함된 경우 알고리즘은 다음 후에 이를 감지할 수 있습니다. N-1 음의 사이클이 가장 짧은 경로 길이를 방해하기 때문입니다.

요약하면, 완화된 가장자리 N-1 Bellman-Ford 알고리즘의 횟수는 알고리즘이 최대 길이의 가능한 모든 경로를 탐색했음을 보장합니다. N-1 , 이는 그래프에서 최단 경로의 가능한 최대 길이입니다. N 정점. 이를 통해 알고리즘은 음의 가중치 주기가 없는 경우 소스 정점에서 다른 모든 정점까지의 최단 경로를 올바르게 계산할 수 있습니다.

N번째 이완에서 거리 감소가 음의 순환이 존재함을 나타내는 이유는 무엇입니까?

이전에 설명한 것처럼 다른 모든 노드에 대한 단일 소스 최단 경로를 달성하려면 다음이 필요합니다. N-1 휴식. N번째 완화로 인해 임의의 노드에 대한 최단 거리가 더 줄어들면 음의 가중치를 갖는 특정 간선이 한 번 더 통과되었음을 의미합니다. 주의할 점은 다음과 같습니다. N-1 완화에서는 각 정점이 한 번만 통과한다고 가정했습니다. 그러나 N번째 완화 동안 거리가 감소한다는 것은 정점을 다시 방문한다는 것을 의미합니다.

자바 프로그램 루프

그래프에서 음의 순환을 감지하기 위한 Bellman-Ford 알고리즘의 작동:

아래에 주어진 그래프가 있고 Bellman-Ford를 사용하여 음의 순환이 존재하는지 여부를 찾고 싶다고 가정해 보겠습니다.

초기 그래프

1 단계: 거리 배열 Dist[]를 초기화하여 소스 꼭지점으로부터 각 꼭지점의 최단 거리를 저장합니다. 처음에는 소스의 거리가 0이 되고 다른 정점의 거리는 INFINITY가 됩니다.

거리 배열 초기화

2 단계: 첫 번째 이완 중에 가장자리 이완을 시작합니다.

  • B의 현재 거리> (A의 거리) + (A에서 B까지의 가중치), 즉 무한대> 0 + 5
    • 따라서 거리[B] = 5

1차 휴식

3단계: 2차 휴식 중:
  • D의 현재 거리> (B의 거리) + (B에서 D까지의 가중치), 즉 무한대> 5 + 2
    • 거리[D] = 7
  • C의 현재 거리> (B의 거리) + (B에서 C까지의 가중치), 즉 무한대> 5 + 1
    • 거리[C] = 6

2차 휴식

문자열 길이 자바

4단계: 3차 휴식 중:

  • F의 현재 거리> (D의 거리) + (D에서 F까지의 가중치), 즉 무한대> 7 + 2
    • 거리[F] = 9
  • E의 현재 거리> (C의 거리) + (C에서 E까지의 가중치), 즉 무한대> 6 + 1
    • 거리[E] = 7

3차 휴식

5단계: 4차 휴식 중:

  • D의 현재 거리> (E의 거리) + (E에서 D까지의 가중치) 즉, 7> 7 + (-1)
    • 거리[D] = 6
  • E의 현재 거리> (F의 거리) + (F에서 E까지의 가중치) 즉, 7> 9 + (-3)
    • 거리[E] = 6

4차 휴식

6단계: 5차 휴식 중:

  • F의 현재 거리> (D의 거리) + (F에 대한 D의 가중치) 즉, 9> 6 + 2
    • 거리[F] = 8
  • D의 현재 거리> (E의 거리) + (E에서 D까지의 가중치) 즉, 6> 6 + (-1)
    • 거리[D] = 5
  • 그래프 h는 정점이 6개이므로 5차 완화 동안 모든 정점에 대한 최단 거리가 계산되어야 합니다.

5차 휴식

7단계: 이제 최종 완화, 즉 6차 완화는 5차 완화의 거리 배열에 변화가 있는 경우 음의 순환이 있음을 나타내야 합니다.

6차 휴식 중에는 다음과 같은 변화가 나타납니다.

  • E의 현재 거리> (F의 거리) + (E에 대한 F의 가중치) 즉, 6> 8 + (-3)
    • 거리[E]=5
  • F의 현재 거리> (D의 거리) + (F에 대한 D의 가중치) 즉, 8> 5 + 2
    • 거리[F]=7

우리는 Distance 배열의 변화를 관찰하므로 그래프에 음의 순환이 존재한다는 결론을 내릴 수 있습니다.

여섯번째 휴식

fcfs

결과: 그래프에는 음의 순환(D->F->E)이 존재합니다.

Bellman-Ford를 사용하여 방향 가중 그래프에서 음의 순환을 찾는 알고리즘:

  • 각 꼭짓점 '에 대해 거리 배열 dist[]를 초기화합니다. ~에 ' 처럼 거리[v] = 무한대 .
  • 임의의 정점('0'이라고 가정)을 소스로 가정하고 할당합니다. 거리 = 0 .
  • 모두 긴장을 풀어라 모서리(u,v,가중치) N-1 아래 조건에 따라 횟수:
    • 거리[v] = 최소(거리[v], 거리[u] + 무게)
  • 이제 모든 가장자리를 다시 한 번 완화합니다. N번째 시간과 아래 두 가지 경우를 기반으로 부정적인 사이클을 감지할 수 있습니다.
    • 사례 1(음의 순환이 존재함): 모서리(u, v, 무게), 거리[u] + 무게인 경우
    • 사례 2(음의 순환 없음): 사례 1은 모든 가장자리에 대해 실패합니다.

알고리즘에서 연결이 끊긴 그래프 처리:

위의 알고리즘과 프로그램은 해당 그래프의 연결이 끊어지면 작동하지 않을 수 있습니다. 소스 정점에서 모든 정점에 도달할 수 있을 때 작동합니다. 0 .
연결이 끊긴 그래프를 처리하기 위해 정점에 대해 위의 알고리즘을 반복할 수 있습니다. 거리 = 무한대, 또는 단순히 방문하지 않은 정점에 대해.

다음은 위의 접근 방식을 구현한 것입니다.

C++ 
// A C++ program for Bellman-Ford's single source // shortest path algorithm. #include  using namespace std; // a structure to represent a weighted edge in graph struct Edge {  int src, dest, weight; }; // a structure to represent a connected, directed and // weighted graph struct Graph {  // V->정점 수, E-> 가장자리 수 int V, E;  // 그래프는 가장자리의 배열로 표현됩니다.  구조체 Edge* 가장자리; }; // V 꼭지점과 E 모서리를 가진 그래프를 생성합니다. struct Graph* createGraph(int V, int E) { struct Graph* graph = new Graph;  그래프->V = V;  그래프->E = E;  그래프->가장자리 = 새 가장자리[E];  그래프 반환; } // 솔루션을 인쇄하는 데 사용되는 유틸리티 함수 void printArr(int dist[], int n) { printf('Vertex Distance from Source
');  for (int i = 0; i< n; ++i)  printf('%d 		 %d
', i, dist[i]); } // The main function that finds shortest distances from src // to all other vertices using Bellman-Ford algorithm. The // function also detects negative weight cycle void BellmanFord(struct Graph* graph, int src) {  int V = graph->V;  int E = 그래프->E;  int 거리[V];  // 1단계: src에서 다른 모든 정점까지의 거리를 // INFINITE로 초기화 for (int i = 0; i< V; i++)  dist[i] = INT_MAX;  dist[src] = 0;  // Step 2: Relax all edges |V| - 1 times. A simple  // shortest path from src to any other vertex can have  // at-most |V| - 1 edges  for (int i = 1; i <= V - 1; i++) {  for (int j = 0; j < E; j++) {  int u = graph->가장자리[j].src;  int v = 그래프->edge[j].dest;  int 가중치 = 그래프->edge[j].weight;  if (dist[u] != INT_MAX && dist[u] + 무게< dist[v])  dist[v] = dist[u] + weight;  }  }  // Step 3: check for negative-weight cycles. The above  // step guarantees shortest distances if graph doesn't  // contain negative weight cycle. If we get a shorter  // path, then there is a cycle.  for (int i = 0; i < E; i++) {  int u = graph->가장자리[i].src;  int v = 그래프->가장자리[i].dest;  int 가중치 = 그래프->edge[i].weight;  if (dist[u] != INT_MAX && dist[u] + 무게< dist[v]) {  printf('Graph contains negative weight cycle');  return; // If negative cycle is detected, simply  // return  }  }  printArr(dist, V);  return; } // Driver's code int main() {  /* Let us create the graph given in above example */  int V = 5; // Number of vertices in graph  int E = 8; // Number of edges in graph  struct Graph* graph = createGraph(V, E);  // add edge 0-1 (or A-B in above figure)  graph->가장자리[0].src = 0;  그래프->가장자리[0].dest = 1;  그래프->가장자리[0].weight = -1;  // 가장자리 0-2(또는 위 그림의 A-C) 추가 graph->edge[1].src = 0;  그래프->가장자리[1].dest = 2;  그래프->가장자리[1].weight = 4;  // 가장자리 1-2(또는 위 그림에서는 B-C) ​​추가 graph->edge[2].src = 1;  그래프->가장자리[2].dest = 2;  그래프->가장자리[2].weight = 3;  // 가장자리 1-3(또는 위 그림에서는 B-D) 추가 graph->edge[3].src = 1;  그래프->가장자리[3].dest = 3;  그래프->가장자리[3].weight = 2;  // 가장자리 1-4(또는 위 그림에서는 B-E) 추가 graph->edge[4].src = 1;  그래프->가장자리[4].dest = 4;  그래프->가장자리[4].weight = 2;  // 가장자리 3-2(또는 위 그림에서는 D-C) 추가 graph->edge[5].src = 3;  그래프->가장자리[5].dest = 2;  그래프->가장자리[5].weight = 5;  // 가장자리 3-1(또는 위 그림에서는 D-B) 추가 graph->edge[6].src = 3;  그래프->가장자리[6].dest = 1;  그래프->가장자리[6].weight = 1;  // 가장자리 4-3(또는 위 그림에서는 E-D) 추가 graph->edge[7].src = 4;  그래프->가장자리[7].dest = 3;  그래프->가장자리[7].weight = -3;    // 함수 호출 BellmanFord(graph, 0);  0을 반환합니다. }>
자바 
// A Java program for Bellman-Ford's single source shortest // path algorithm. import java.io.*; import java.lang.*; import java.util.*; // A class to represent a connected, directed and weighted // graph class Graph {    // A class to represent a weighted edge in graph  class Edge {  int src, dest, weight;  Edge() { src = dest = weight = 0; }  };  int V, E;  Edge edge[];  // Creates a graph with V vertices and E edges  Graph(int v, int e)  {  V = v;  E = e;  edge = new Edge[e];  for (int i = 0; i < e; ++i)  edge[i] = new Edge();  }  // The main function that finds shortest distances from  // src to all other vertices using Bellman-Ford  // algorithm. The function also detects negative weight  // cycle  void BellmanFord(Graph graph, int src)  {  int V = graph.V, E = graph.E;  int dist[] = new int[V];  // Step 1: Initialize distances from src to all  // other vertices as INFINITE  for (int i = 0; i < V; ++i)  dist[i] = Integer.MAX_VALUE;  dist[src] = 0;  // Step 2: Relax all edges |V| - 1 times. A simple  // shortest path from src to any other vertex can  // have at-most |V| - 1 edges  for (int i = 1; i < V; ++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] != Integer.MAX_VALUE  && dist[u] + weight < dist[v])  dist[v] = dist[u] + weight;  }  }  // Step 3: check for negative-weight cycles. The  // above step guarantees shortest distances if graph  // doesn't contain negative weight cycle. If we get  // a shorter path, then there is a cycle.  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] != Integer.MAX_VALUE  && dist[u] + weight < dist[v]) {  System.out.println(  'Graph contains negative weight cycle');  return;  }  }  printArr(dist, V);  }  // A utility function used to print the solution  void printArr(int dist[], int V)  {  System.out.println('Vertex Distance from Source');  for (int i = 0; i < V; ++i)  System.out.println(i + '		' + dist[i]);  }  // Driver's code  public static void main(String[] args)  {  int V = 5; // Number of vertices in graph  int E = 8; // Number of edges in graph  Graph graph = new Graph(V, E);  // add edge 0-1 (or A-B in above figure)  graph.edge[0].src = 0;  graph.edge[0].dest = 1;  graph.edge[0].weight = -1;  // add edge 0-2 (or A-C in above figure)  graph.edge[1].src = 0;  graph.edge[1].dest = 2;  graph.edge[1].weight = 4;  // add edge 1-2 (or B-C in above figure)  graph.edge[2].src = 1;  graph.edge[2].dest = 2;  graph.edge[2].weight = 3;  // add edge 1-3 (or B-D in above figure)  graph.edge[3].src = 1;  graph.edge[3].dest = 3;  graph.edge[3].weight = 2;  // add edge 1-4 (or B-E in above figure)  graph.edge[4].src = 1;  graph.edge[4].dest = 4;  graph.edge[4].weight = 2;  // add edge 3-2 (or D-C in above figure)  graph.edge[5].src = 3;  graph.edge[5].dest = 2;  graph.edge[5].weight = 5;  // add edge 3-1 (or D-B in above figure)  graph.edge[6].src = 3;  graph.edge[6].dest = 1;  graph.edge[6].weight = 1;  // add edge 4-3 (or E-D in above figure)  graph.edge[7].src = 4;  graph.edge[7].dest = 3;  graph.edge[7].weight = -3;    // Function call  graph.BellmanFord(graph, 0);  } } // Contributed by Aakash Hasija>
파이썬3 
# Python3 program for Bellman-Ford's single source # shortest path algorithm. # Class to represent a graph class Graph: def __init__(self, vertices): self.V = vertices # No. of vertices self.graph = [] # function to add an edge to graph def addEdge(self, u, v, w): self.graph.append([u, v, w]) # utility function used to print the solution def printArr(self, dist): print('Vertex Distance from Source') for i in range(self.V): print('{0}		{1}'.format(i, dist[i])) # The main function that finds shortest distances from src to # all other vertices using Bellman-Ford algorithm. The function # also detects negative weight cycle def BellmanFord(self, src): # Step 1: Initialize distances from src to all other vertices # as INFINITE dist = [float('Inf')] * self.V dist[src] = 0 # Step 2: Relax all edges |V| - 1 times. A simple shortest # path from src to any other vertex can have at-most |V| - 1 # edges for _ in range(self.V - 1): # Update dist value and parent index of the adjacent vertices of # the picked vertex. Consider only those vertices which are still in # queue for u, v, w in self.graph: if dist[u] != float('Inf') and dist[u] + w < dist[v]: dist[v] = dist[u] + w # Step 3: check for negative-weight cycles. The above step # guarantees shortest distances if graph doesn't contain # negative weight cycle. If we get a shorter path, then there # is a cycle. for u, v, w in self.graph: if dist[u] != float('Inf') and dist[u] + w < dist[v]: print('Graph contains negative weight cycle') return # print all distance self.printArr(dist) # Driver's code if __name__ == '__main__': g = Graph(5) g.addEdge(0, 1, -1) g.addEdge(0, 2, 4) g.addEdge(1, 2, 3) g.addEdge(1, 3, 2) g.addEdge(1, 4, 2) g.addEdge(3, 2, 5) g.addEdge(3, 1, 1) g.addEdge(4, 3, -3) # function call g.BellmanFord(0) # Initially, Contributed by Neelam Yadav # Later On, Edited by Himanshu Garg>
씨# 
// C# program for Bellman-Ford's single source shortest // path algorithm. using System; // A class to represent a connected, directed and weighted // graph class Graph {  // A class to represent a weighted edge in graph  class Edge {  public int src, dest, weight;  public Edge() { src = dest = weight = 0; }  };  int V, E;  Edge[] edge;  // Creates a graph with V vertices and E edges  Graph(int v, int e)  {  V = v;  E = e;  edge = new Edge[e];  for (int i = 0; i < e; ++i)  edge[i] = new Edge();  }  // The main function that finds shortest distances from  // src to all other vertices using Bellman-Ford  // algorithm. The function also detects negative weight  // cycle  void BellmanFord(Graph graph, int src)  {  int V = graph.V, E = graph.E;  int[] dist = new int[V];  // Step 1: Initialize distances from src to all  // other vertices as INFINITE  for (int i = 0; i < V; ++i)  dist[i] = int.MaxValue;  dist[src] = 0;  // Step 2: Relax all edges |V| - 1 times. A simple  // shortest path from src to any other vertex can  // have at-most |V| - 1 edges  for (int i = 1; i < V; ++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.MaxValue  && dist[u] + weight < dist[v])  dist[v] = dist[u] + weight;  }  }  // Step 3: check for negative-weight cycles. The  // above step guarantees shortest distances if graph  // doesn't contain negative weight cycle. If we get  // a shorter path, then there is a cycle.  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.MaxValue  && dist[u] + weight < dist[v]) {  Console.WriteLine(  'Graph contains negative weight cycle');  return;  }  }  printArr(dist, V);  }  // A utility function used to print the solution  void printArr(int[] dist, int V)  {  Console.WriteLine('Vertex Distance from Source');  for (int i = 0; i < V; ++i)  Console.WriteLine(i + '		' + dist[i]);  }  // Driver's code  public static void Main()  {  int V = 5; // Number of vertices in graph  int E = 8; // Number of edges in graph  Graph graph = new Graph(V, E);  // add edge 0-1 (or A-B in above figure)  graph.edge[0].src = 0;  graph.edge[0].dest = 1;  graph.edge[0].weight = -1;  // add edge 0-2 (or A-C in above figure)  graph.edge[1].src = 0;  graph.edge[1].dest = 2;  graph.edge[1].weight = 4;  // add edge 1-2 (or B-C in above figure)  graph.edge[2].src = 1;  graph.edge[2].dest = 2;  graph.edge[2].weight = 3;  // add edge 1-3 (or B-D in above figure)  graph.edge[3].src = 1;  graph.edge[3].dest = 3;  graph.edge[3].weight = 2;  // add edge 1-4 (or B-E in above figure)  graph.edge[4].src = 1;  graph.edge[4].dest = 4;  graph.edge[4].weight = 2;  // add edge 3-2 (or D-C in above figure)  graph.edge[5].src = 3;  graph.edge[5].dest = 2;  graph.edge[5].weight = 5;  // add edge 3-1 (or D-B in above figure)  graph.edge[6].src = 3;  graph.edge[6].dest = 1;  graph.edge[6].weight = 1;  // add edge 4-3 (or E-D in above figure)  graph.edge[7].src = 4;  graph.edge[7].dest = 3;  graph.edge[7].weight = -3;    // Function call  graph.BellmanFord(graph, 0);  }  // This code is contributed by Ryuga }>
자바스크립트 
// a structure to represent a connected, directed and // weighted graph class Edge {  constructor(src, dest, weight) {  this.src = src;  this.dest = dest;  this.weight = weight;  } } class Graph {  constructor(V, E) {  this.V = V;  this.E = E;  this.edge = [];  } } function createGraph(V, E) {  const graph = new Graph(V, E);  for (let i = 0; i < E; i++) {  graph.edge[i] = new Edge();  }  return graph; } function printArr(dist, V) {  console.log('Vertex Distance from Source');  for (let i = 0; i < V; i++) {  console.log(`${i} 		 ${dist[i]}`);  } } function BellmanFord(graph, src) {  const V = graph.V;  const E = graph.E;  const dist = [];  for (let i = 0; i < V; i++) {  dist[i] = Number.MAX_SAFE_INTEGER;  }  dist[src] = 0;  for (let i = 1; i <= V - 1; i++) {  for (let j = 0; j < E; j++) {  const u = graph.edge[j].src;  const v = graph.edge[j].dest;  const weight = graph.edge[j].weight;  if (dist[u] !== Number.MAX_SAFE_INTEGER && dist[u] + weight < dist[v]) {  dist[v] = dist[u] + weight;  }  }  }  for (let i = 0; i < E; i++) {  const u = graph.edge[i].src;  const v = graph.edge[i].dest;  const weight = graph.edge[i].weight;  if (dist[u] !== Number.MAX_SAFE_INTEGER && dist[u] + weight < dist[v]) {  console.log('Graph contains negative weight cycle');  return;  }  }  printArr(dist, V); } // Driver program to test methods of graph class   // Create a graph given in the above diagram const V = 5; const E = 8; const graph = createGraph(V, E); graph.edge[0] = new Edge(0, 1, -1); graph.edge[1] = new Edge(0, 2, 4); graph.edge[2] = new Edge(1, 2, 3); graph.edge[3] = new Edge(1, 3, 2); graph.edge[4] = new Edge(1, 4, 2); graph.edge[5] = new Edge(3, 2, 5); graph.edge[6] = new Edge(3, 1, 1); graph.edge[7] = new Edge(4, 3, -3); BellmanFord(graph, 0);>
산출 
Vertex Distance from Source 0 0 1 -1 2 2 3 -2 4 1>

Bellman-Ford 알고리즘의 복잡성 분석 :

  • 그래프 연결 시 시간 복잡도:
    • 최선의 경우: O(E), 1차 완화 후의 거리 배열과 2차 완화 후의 거리 배열이 동일하면 간단히 추가 처리를 중지할 수 있습니다.
    • 평균 사례: 오(V*E)
    • 최악의 경우: O(V*E)
  • 그래프 연결이 끊어졌을 때의 시간 복잡도 :
    • 모든 경우: O(E*(V^2))
  • 보조 공간: O(V), 여기서 V는 그래프의 정점 수입니다.

Bellman Ford의 알고리즘 애플리케이션:

  • 네트워크 라우팅: Bellman-Ford는 컴퓨터 네트워킹에서 라우팅 테이블의 최단 경로를 찾는 데 사용되어 데이터 패킷이 네트워크에서 효율적으로 탐색되도록 돕습니다.
  • GPS 내비게이션: GPS 장치는 Bellman-Ford를 사용하여 위치 간의 최단 또는 가장 빠른 경로를 계산하여 내비게이션 앱 및 장치를 지원합니다.
  • 운송 및 물류: Bellman-Ford의 알고리즘을 적용하면 운송 및 물류 분야에서 차량의 최적 경로를 결정하고 연료 소비와 이동 시간을 최소화할 수 있습니다.
  • 게임 개발: Bellman-Ford는 다양한 경로에 다양한 비용이나 장애물이 있을 수 있는 게임 개발 시 가상 세계 내에서 이동 및 탐색을 모델링하는 데 사용할 수 있습니다.
  • 로봇공학 및 자율주행차: 이 알고리즘은 장애물, 지형, 에너지 소비를 고려하여 로봇이나 자율주행차의 경로 계획을 지원합니다.

Bellman Ford 알고리즘의 단점:

  • 그래프에 음의 에지 사이클이 포함되어 있으면 Bellman-Ford 알고리즘이 실패합니다.

단일 소스 최단 경로 알고리즘 관련 기사: