🔔 Bellman-Ford algorithm

Bellman's Equation

Bellman's equation을 기반으로 시행하는 알고리즘이다.
Bellman's equation은 다음과 같다.

여기서 i와 j는 각각 i가 Source node, j가 adjacent node라고 생각할 수 있다. 여기서 source는 1이다. 또한, node끼리 연결되어 있지 않다면 그 node 사이의 길이는 무한대로 표시한다.

쉽게 예를 들어보자. 서울에서 부산까지 가는 최단 경로를 Bellman-Ford algorithm으로 구하고 싶다. 이때, 서울에서 부산으로 갈 때 거치는 주유소가 수원과 원주, 인천이 있다고 해보자. 이 주유소를 거치지 않는다면 부산까지 갈 수 없다. 이 상황에서 각 변수와 다음 예시를 매칭해보자.

• D_i = 서울에서 부산까지의 거리
• D_j = 원주, 수원, 인천 = 주유소
• d_ji = 서울에서 주유소까지의 각 거리들

이렇게 보면 서울에서 부산까지 가는 최단경로는 각 주유소에서부터 부산까지의 거리와 서울에서 주유소까지의 거리를 합한 값 중에 가장 작은 값이 최단 경로가 될 것이다.

이렇게 말로 풀어서 보면 너무도 당연하지만, 서울 입장에서는 주유소까지의 거리는 알지만, 주유소에서 부산까지의 거리는 알 수 없다는 가정이 전제되어 있다. 그렇기 때문에 주유소에서 알려주는 정보(주유소에서부터 부산까지의 거리)를 참고하여 최단 경로를 선택해야 한다.

Bellman-Ford Algorithm

이건 처음부터 시작해서 i를 Source node로 두고, h 즉 최대로 거칠 수 있는 arc의 수를 하나씩 늘려가면서 기존 시행보다 더 낮은 값을 도출해낸다면 D_i를 업데이트 한다.

Ⰾ Dijkstra's Algorithm

이 알고리즘은 MST를 만드는 Prim 방법과 유사한 과정을 가진다. 경로 P의 집합을 업데이트 해가면서 최단 경로를 찾아간다.

🌊 Floyd-Warshall Algorithm

Floyd-Warshall은 i 노드에서 j 노드로 갈 때 n+1번 노드를 거치는 경로의 값을 차례대로 계산해서 기존 값과 비교해서 더 작은 값을 반영한다. 이렇게 되면 모든 노드를 거치는 경로들을 탐색했을 때 나오는 값이 가장 최단 경로 값이 된다.