최단 경로 탐색 알고리즘 : 다익스트라, 벨만-포드, 플로이드-워셜

 

라우팅 프로토콜의 근간이 되는 최단 경로(Shortest Path) 탐색 알고리즘을 정리합니다. 대표적인 '단일 출발 최단 경로(Single-Source Shortest Path)' 알고리즘인 다익스트라와 벨만-포드, 그리고 '모든 쌍 최단 경로(All-Pairs Shortest Path)' 알고리즘인 플로이드-워셜의 핵심 원리와 차이점을 알아보겠습니다.

---

## 1. 다익스트라 (Dijkstra) 알고리즘

다익스트라 알고리즘은 음수 가중치(Negative Weight) 간선이 없는 그래프에서 특정 노드로부터 다른 모든 노드까지의 최단 경로를 찾는 대표적인 탐욕(Greedy) 알고리즘입니다. 🛣️

### 핵심 아이디어: 선택과 확산

"가장 가까운 곳부터 차례대로 방문한다"는 원칙을 따릅니다. 즉, 현재까지 알려진 '방문하지 않은 노드'들 중에서 출발지로부터의 거리가 가장 짧은 노드를 하나 선택합니다. 그 노드의 최단 경로를 **'확정'**하고, 해당 노드를 거쳐갈 때 더 짧아지는 경로가 있는지 주변 노드들의 값을 갱신하는 '선택과 확정' 과정을 반복합니다.

### 동작 과정

1. 초기화: 출발 노드의 거리는 0, 나머지는 무한대(∞)로 설정하고 우선순위 큐에 모든 노드를 넣습니다.
2. 반복: 큐가 빌 때까지 다음을 반복합니다.
   1. 큐에서 현재 가장 거리가 짧은 노드 u를 꺼내 방문 처리합니다.
   2. u를 거쳐 u의 인접 노드 v로 가는 경로가 기존 v까지의 경로보다 짧다면, v의 거리를 갱신하고 큐에 반영합니다(Relaxation).

### 주요 특징

• 전제 조건: 모든 간선의 가중치는 양수여야 합니다.
• 시간 복잡도: 우선순위 큐 사용 시 O(E log V).
• 대표 프로토콜: OSPF와 같은 링크 상태(Link-State) 라우팅 프로토콜에서 사용됩니다.

---

## 2. 벨만-포드 (Bellman-Ford) 알고리즘

벨만-포드 알고리즘은 음수 가중치 간선이 포함된 그래프에서도 동작하며, 음수 사이클(Negative Cycle)의 존재 여부까지 탐지할 수 있는 강력한 알고리즘입니다.

### 핵심 아이디어: 반복적 총점검

동적 프로그래밍(Dynamic Programming) 접근 방식을 사용합니다. "최단 경로는 최대 (V-1)개의 간선으로 이루어진다"는 원리를 이용하여, 전체 간선에 대한 완화(Relaxation) 작업을 (V-1)번 반복하는 것이 핵심입니다.

### 동작 과정

1. 초기화: 출발 노드의 거리는 0, 나머지는 무한대(∞)로 설정합니다.
2. 전체 간선 반복: 총 (V-1)번 동안, 그래프에 존재하는 모든 간선에 대해 완화 작업을 수행합니다.
3. (음수 사이클 탐지): (V-1)번 반복 후, 추가로 한 번 더 모든 간선을 확인했을 때 경로 값이 또 갱신된다면, 그래프 내에 음수 사이클이 존재한다고 판단합니다.

### 주요 특징

• 음수 가중치 처리: 음수 가중치 간선을 포함한 그래프에서도 최단 경로를 올바르게 찾을 수 있습니다.
• 시간 복잡도: O(V * E), 다익스트라보다 느립니다.
• 대표 프로토콜: RIP와 같은 거리 벡터(Distance-Vector) 라우팅 프로토콜의 기반이 됩니다.

---

## 3. 다익스트라 vs. 벨만-포드 한눈에 비교

구분	다익스트라 (Dijkstra)	벨만-포드 (Bellman-Ford)
핵심 방식	탐욕 (Greedy) 알고리즘	동적 프로그래밍 (Dynamic Programming)
음수 가중치	❌ 불가능	✅ 가능
음수 사이클	❌ 탐지 불가	✅ 탐지 가능
시간 복잡도	O(E log V) (상대적으로 빠름)	O(V * E) (상대적으로 느림)
대표 프로토콜	OSPF	RIP

 

※ 공통점: 두 알고리즘 모두 단일 출발지 최단 경로를 구하므로, 다른 노드에서 출발하는 경로를 알고 싶다면 해당 노드를 출발점으로 다시 알고리즘을 실행해야 합니다.

---

## 4. 모든 쌍 최단 경로: 플로이드-워셜 (Floyd-Warshall)

그렇다면 모든 노드를 출발지로 하는 최단 경로를 한 번에 알고 싶다면 어떻게 해야 할까요? 이럴 때 사용하는 것이 바로 '모든 쌍 최단 경로(All-Pairs Shortest Path)' 알고리즘인 플로이드-워셜입니다. 🗺️

### 핵심 아이디어

"노드 i에서 j로 가는 최단 경로는, 중간에 특정 경유지 k를 거쳐 가는 경로와 비교해서 더 짧은 쪽으로 계속 갱신된다."

모든 노드(k)를 잠재적인 경유지로 하나씩 고려하면서, i → j로 바로 가는 기존 경로와 i → k → j로 거쳐 가는 새로운 경로 중 더 짧은 값을 선택하여 V x V 거리 행렬을 점진적으로 완성합니다.

### 동작 과정

V x V 크기의 거리 행렬을 초기화한 뒤, 3중 반복문을 통해 모든 최단 경로를 갱신합니다.

for k in 1...V:      // 경유지 노드
  for i in 1...V:    // 출발 노드
    for j in 1...V:  // 도착 노드
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

### 주요 특징

• 음수 가중치 처리: 벨만-포드처럼 음수 가중치 간선을 처리할 수 있습니다.
• 시간 복잡도: O(V^3). 노드 개수가 적고 간선이 많은 **밀집 그래프(Dense Graph)**에 적합합니다.