[알고리즘] 벨만-포드(bellman-ford-moore)

1. 벨만-포드 알고리즘이란

그래프에서 최단 거리를 구하는 알고리즘

 

2. 특징

• 음수 가중치 에지가 있어도 로직이 수행이 가능하다.
• 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있다.

 

3. 알고리즘 로직

1) 주어진 데이터를 Edge리스트로 그래프로 구현한 후, 거리 배열의 값을 업데이트한다.

• Edge를 중심으로 동작하기 때문에 그래프를 Edge리스트로 구현한다.
• 최단 경로 배열은 출발노드는 0, 나머지는 무한대(99,999,999 혹은 INF)로 초기화한다.
• 출발 노드가 방문한 적 없는 노드일 때는 값을 업데이트 하지 않는다.
• if(출발 노드의 거리 배열의 값 + Edge 가중치 <  종료 노드의 거리 배열값) 거리 배열 값 업데이트

2) 노드 개수 - 1번만큼 1)을 반복한다.

• 최단 거리 배열에서 업데이트의 반복 횟수는 노드 개수 - 1번이다.
  • 이유는 음수 사이클이 없을 때, 특정한 두 노드의 최단 거리를 구성할 수 있는 Edge의 최대 개수가 n-1개이기 때문이다.
• 전체 간선 E개를 하나씩 확인 하여 각 간선을 거쳐 다른 노드로 가는 비용을 계산, 최단 거리 배열을 업데이트한다.

3) 음수 사이클 유무 확인하기

• 모든 Edge에 대해 1)의 과정을 한 번 더 수행하여 음수 사이클이 발생하는지 확인한다.
• 업데이트 되는 노드가 있다면, 음수 사이클이 있다는 뜻이다. 
• 이 말은 즉, 2)에서 계산한 정답 배열이 무의미하다 == 최단 거리를 찾을 수 없는 그래프 라는 뜻이다.

 

4. 다익스트라 알고리즘과의 차이점

1) 다익스트라

• 매번 방문하지 않은 노드 중, 최단 거리가 가장 짧은 노드를 선택한다.
• 음수 간선이 없는 경우, 최적의 해를 구할 수 있다.

2) 벨만-포드

• 매번 모든 간선을 전부 확인한다.
  • 이 말은 다익스트라에서의 최적의 해를 항상 포함한다는 뜻이다.
• 다익스트라에 비해 오래 걸린다. 하지만 음수 사이클을 확인할 수 있다.

 

5. 문제와 함께 코드 확인

[백준][골드][벨만포드] 11657 타임머신

 

6. 시간복잡도 : O(VE) 

다익스트라에 비해 느리다.

 

 

 

[알고리즘] 다익스트라(Dijkstra)