[알고리즘] 벨먼-포드 알고리즘

✅ 벨먼-포드 알고리즘 (Bellman-Ford Algorithm)

❕ 기본 개념 

- 그래프의 최단 경로 문제를 해결하기 위한 알고리즘

- 최단 경로 문제에서는 간선에 가중치가 부여된 가중 그래프가 주어지며,

시작점부터 종점까지의 경로 중 간선의 가중치 최소합을 구하면 됨

- 가중치가 음수라도 제대로 동작함

- 방향성/비방향성 그래프 모두 적용 가능

- 정점 수를 n, 간선 수를 m이라고 할 때, 가중치 변경 작업을 n회 순회하고,

각 변경 작업에서 각 간선을 1회씩 조사하므로 전체 계산 시간은 O(nm)

 

 

❕ 작동 방식 

 

 

작동 예시

 

 

 

✔ 구현 방법 (JS) 

function BellmanFord(graph, V, E, src) {
  // Initialize distance of all vertices as infinite.
  var dis = Array(V).fill(1000000000);

  // initialize distance of source as 0
  dis[src] = 0;

  // Relax all edges |V| - 1 times. A simple
  // shortest path from src to any other
  // vertex can have at-most |V| - 1 edges
  for (var i = 0; i < V - 1; i++) {
    for (var j = 0; j < E; j++) {
      if (dis[graph[j][0]] + graph[j][2] < dis[graph[j][1]])
        dis[graph[j][1]] = dis[graph[j][0]] + graph[j][2];
    }
  }

  // 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 (var i = 0; i < E; i++) {
    var x = graph[i][0];
    var y = graph[i][1];
    var weight = graph[i][2];
    if (dis[x] != 1000000000 && dis[x] + weight < dis[y])
      document.write("Graph contains negative" + " weight cycle<br>");
  }

  document.write("Vertex Distance from Source<br>");
  for (var i = 0; i < V; i++) document.write(i + "   " + dis[i] + "<br>");
}

// Driver code
var V = 5; // Number of vertices in graph
var E = 8; // Number of edges in graph

// Every edge has three values (u, v, w) where
// the edge is from vertex u to v. And weight
// of the edge is w.
var graph = [
  [0, 1, -1],
  [0, 2, 4],
  [1, 2, 3],
  [1, 3, 2],
  [1, 4, 2],
  [3, 2, 5],
  [3, 1, 1],
  [4, 3, -3],
];
BellmanFord(graph, V, E, 0);


/*
Output

Vertex Distance from Source
0        0
1        -1
2        2
3        -2
4        1
 */

 

 

참고자료

「알고리즘 도감」 中 4-4 벨먼-포드 알고리즘

https://www.programiz.com/dsa/bellman-ford-algorithm

https://wch18735.github.io/algorithm/Bellman_Ford/

https://www.geeksforgeeks.org/bellman-ford-algorithm-simple-implementation/