[최단거리 알고리즘] Bellman Ford, Floyd-Warshall, Dijkstra

알고리즘에서 기본적인 내용인데 매번 헷갈려서 적어두는 글.

 

Single Source Shortest Path Problem 

출발점 하나에서 다른 노드로 가는 최단 거리를 찾을 때는 Bellman Ford,Dijkstra 알고리즘을 사용할 수 있다. 

---

Bellman Ford는 negative arc를 처리할 수 있다. 그러나 negative dicycle은 처리가 불가능하다. 노드가 V개 있을 때 V-1번 이후로 값들이 업데이트 되지 않는다면 negative dicycle이 없는 것이다. 그런데 만일 V번째 iteration에서 값이 변동된다면 negative dicycle이 있는 것이다. 시간 복잡도는 O(VE)이다. 

 

알고리즘은 아래와 같다.

 

1. Initialization:  
   주어진 시작 정점 \( s \)에서 다른 모든 정점까지의 거리를 무한대로 설정하고, 시작 정점의 거리는 0으로 설정한다.
   \[
   d(s) = 0 \quad \text{and} \quad d(v) = \infty \, \forall \, v \neq s
   \]
   여기서 \( d(v) \)는 정점 \( v \)까지의 최단 경로를 나타낸다.

2. Relaxation:  
   i번째 iteration에서는 i 개수만큼의 arc를 거쳐 도달할 수 있는 node들에 대해 arc의 비용을 갱신한다. 이 과정을 정점의 개수 \( V \)에 대해 \( V - 1 \)번 반복한다.
   
   경로가 갱신되는 조건은:
   \[
   d(v) > d(u) + w(u, v)
   \]
   여기서 \( w(u, v) \)는 간선 \( (u, v) \)의 가중치이고 위 조건이 만족되면 아래와 같이 갱신한다:
   \[
   d(v) = d(u) + w(u, v)
   \]

3. 음수 사이클 확인:  
   만약 어느 간선에 대해서도 다음 조건이 성립하면 그래프에 음수 사이클이 존재한다는 뜻이다.
   \[
   d(v) > d(u) + w(u, v)
   \]

 

일반적으로 그냥 V-1번동안 모든 노드를 탐색하라고 써놓은 글들도 많던데 그렇게 하는 것은 효율적이진 않다. 

 

예를 들어 위 그림에서 첫번째 iteration이 이루어졌다고 생각해보자. 어차피 t노드는 그 전 노드들인 b와 d가 업데이트가 되어야 변동이 있을것이다. 따라서 t까지 굳이 살펴볼 필요가 없다. 따라서 매 iteration마다 iteration숫자만큼의 arc를 거쳐 도달할 수 있는 노드들까지만 업데이트 하는 것으로 충분한 것이다.  

---

Dijkstra 알고리즘 

 

다익스트라 알고리즘 역시 Single Source Shortest Path Problem을 해결하는데 사용될 수 있다. 다만 차이점은 negative arc를 처리하지 못하고 그래서 당연히 negative dicycle 역시 처리하지 못한다. 또한 negative arc가 없을 때만 사용되기에 한 arc를 한 번씩만 처리하고 재방문하지 않는다. 이를 위해 temporary, 그리고 permanent node라는 개념을 도입하게 된다. Permanent로 지정된 노드들은 재방문 하지 않는다. 알고리즘은 아래와 같다. 

 

1. 초기화 단계:
   시작 정점 \( s \)에서 다른 모든 정점까지의 거리를 무한대로 설정하고, 시작 정점의 거리는 0으로 설정한다.
   \[
   d(s) = 0 \quad \text{and} \quad d(v) = \infty \, \forall \, v \neq s
   \]
   여기서 \( d(v) \)는 정점 \( v \)까지의 최단 경로를 나타낸다.
   
   방문하지 않은 모든 정점을 저장할 집합 \( Q \)를 설정한다.

2. 정점 선택 단계:
   아직 방문하지 않은 정점 중에서 가장 거리가 짧은 정점 \( u \)를 선택한다.
   \[
   u = \arg\min_{v \in Q} d(v)
   \]

3. Relaxation:
   선택된 정점 \( u \)에 연결된 모든 인접 정점 \( v \)에 대해, 다음 조건을 만족하면 거리를 갱신한다. 이때 neighbor v들은  temporary node들이다.
   \[
   d(v) > d(u) + w(u, v)
   \]
   여기서 \( w(u, v) \)는 간선 \( (u, v) \)의 가중치이다. 조건이 성립하면 거리를 다음과 같이 업데이트한다.
   \[
   d(v) = d(u) + w(u, v)
   \]

4. 정점 고정 단계:
   정점 \( u \)를 방문한 정점으로 표시하고 (Permanent Node로 고정), 집합 \( Q \)에서 제거한다다.
   
5. 반복:
   모든 정점을 방문할 때까지 2-4 과정을 반복한다.

 

시간 복잡도는 O(V^2)이고 priority queue를 사용하면 O(V + ElogE)로 줄일 수 있다.

---

Floyd-Warshall

 

Floyd-Warshall 알고리즘은 All to All shortest path 문제를 해결할 수 있다. 또한 negative dicycle을 handle할 수 있다. 알고리즘은 아래와 같다. 

 

1. 초기화 단계:
   그래프의 인접 행렬 \( D \)를 다음과 같이 초기화된다.
   - \( D[i][j] = w(i, j) \), 만약 \( i \)에서 \( j \)로 간선이 있을 때 가중치 \( w(i, j) \).
   - \( D[i][j] = \infty \), 간선이 존재하지 않으면.
   - \( D[i][i] = 0 \), 자기 자신으로의 경로는 0.

2. 경로 갱신 단계 (삼중 반복문):
   모든 정점 \( k \), \( i \), \( j \)에 대해, 정점 \( i \)에서 \( j \)까지의 최단 경로가 정점 \( k \)를 거쳐서 더 짧아지는지 확인하고, 경로를 갱신한다.
   \[
   D[i][j] = \min(D[i][j], D[i][k] + D[k][j])
   \]
   즉, 정점 \( i \)에서 \( j \)까지의 최단 경로는, 현재 알려진 경로 \( D[i][j] \)와 \( i \to k \to j \) 경로 중 더 작은 값을 선택하여 갱신한다.

3. 음수 사이클 확인:
   경로 갱신 후, \( D[i][i] < 0 \)인 경우, 정점 \( i \)가 음수 사이클에 포함되어 있다는 것을 의미한다.

4. 최종 결과:
   모든 쌍에 대한 최단 경로가 계산된다.

 

Floyd-Warshall 알고리즘의 시간 복잡도는 삼중 반복문을 사용하기 때문에 \( O(V^3) \)이다. 그 이유는 각 정점마다 major iteration이 돌아가고 매 iteration동안 모든 arc(정점과 정점 사이의 모든 arc)를 고려하기 떄문에 총 \( V^3 \)번의 연산이 필요하다.