컴퓨터 네트워크에서 최단 경로(Shortest Path) 알고리즘은 네트워크 노드 사이에서 라우팅 비용을 최소화하는 최적의 경로를 찾는 것을 목표로 합니다. 그래프 이론에서 제안된 최단 경로 알고리즘을 네트워크 라우팅에 직접 적용한 것으로, 실제 라우팅 프로토콜의 핵심 동작 원리가 됩니다.
최단 경로 알고리즘의 기본 개념
네트워크를 N개의 정점(노드 또는 네트워크 장비)이 M개의 간선(전송 선로)으로 연결된 그래프라고 가정해 보겠습니다. 각 간선에는 해당 전송 선로의 물리적 거리나 전송 지연 시간을 나타내는 가중치(weight)가 부여됩니다.
최단 경로 알고리즘의 목표는 임의의 두 정점 사이를 간선을 따라 이동할 때 간선 가중치의 합이 최소가 되는 경로를 찾는 것입니다. 만약 모든 간선의 가중치가 동일하다면, 홉(hop) 수가 가장 적은 경로를 찾게 됩니다.
대표적인 최단 경로 알고리즘
널리 사용되는 최단 경로 알고리즘은 다음과 같습니다.
- 벨만-포드(Bellman-Ford) 알고리즘
- 다익스트라(Dijkstra) 알고리즘
- 플로이드-워셜(Floyd-Warshall) 알고리즘
이제 각 알고리즘의 입력, 출력, 동작 과정을 하나씩 살펴보겠습니다.
벨만-포드(Bellman-Ford) 알고리즘
입력: 네트워크를 나타내는 그래프와 출발 노드 s
출력: s에서 다른 모든 노드까지의 최단 경로
- s에서 모든 노드까지의 거리를 무한대(∞)로 초기화하고, 자기 자신까지의 거리는 0으로 설정합니다. 즉, 크기가 |V|(노드 수)인 배열 dist[]를 만들어 dist[s]를 제외한 모든 값을 ∞로 채웁니다.
- 최단 거리를 반복적으로 계산합니다. s를 제외한 각 노드에 대해 |V|-1회 반복합니다.
- 정점 u와 v를 연결하는 각각의 간선에 대해 다음 조건을 검사합니다.
dist[v] > dist[u] + (간선 u-v의 가중치)라면,
dist[v] = dist[u] + (간선 u-v의 가중치)로 갱신합니다. - 반복이 끝나면 배열 dist[]에는 s에서 다른 모든 노드까지의 최단 경로가 저장됩니다.
벨만-포드 알고리즘은 음의 가중치를 가진 간선도 처리할 수 있다는 장점이 있으며, 거리 벡터(Distance Vector) 방식의 라우팅 프로토콜인 RIP(Routing Information Protocol)의 이론적 기반이 됩니다.
다익스트라(Dijkstra) 알고리즘
입력: 네트워크를 나타내는 그래프와 출발 노드 s
출력: s를 루트 노드로 하는 최단 경로 트리 spt[]
초기화
- 크기가 |V|(노드 수)인 거리 배열 dist[]를 준비합니다. dist[s] = 0이며, s를 제외한 노드 u에 대해서는 dist[u] = ∞(무한대)입니다.
- 그래프의 모든 노드를 담는 배열 Q를 준비합니다. 알고리즘이 종료되면 Q는 비게 됩니다.
- 방문한 노드를 추가할 빈 집합 S를 준비합니다. 알고리즘이 종료되면 S에는 그래프의 모든 노드가 포함됩니다.
동작 과정
- Q가 비어 있지 않은 동안 다음을 반복합니다.
- Q에서 dist[u] 값이 가장 작으면서 아직 S에 속하지 않은 노드 u를 제거합니다. 첫 번째 실행에서는 dist[s]가 선택됩니다.
- u를 S에 추가하여 방문 처리합니다.
- u에 인접한 각 노드 v에 대해 dist[v]를 다음과 같이 갱신합니다.
(dist[u] + 간선 u-v의 가중치) < dist[v]라면,
dist[v] = dist[u] + 간선 u-v의 가중치로 업데이트합니다.
반복이 끝나면 배열 dist[]에는 s에서 다른 모든 노드까지의 최단 경로가 저장됩니다. 다익스트라 알고리즘은 음의 가중치 간선이 없는 경우 빠르게 동작하며, 링크 상태(Link State) 방식의 라우팅 프로토콜인 OSPF(Open Shortest Path First)에서 활용됩니다.
플로이드-워셜(Floyd-Warshall) 알고리즘
입력: 네트워크 내 노드 간 경로를 나타내는 비용 인접 행렬 adj[][]
출력: 그래프의 모든 노드 쌍 사이의 최소 비용 경로를 보여주는 최단 경로 비용 행렬 cost[][]
- cost[][]를 다음과 같이 초기화합니다.
adj[][]가 비어 있으면 cost[][] = ∞(무한대)
그렇지 않으면 cost[][] = adj[][] - N = |V|로 설정합니다. 여기서 V는 네트워크 노드의 집합입니다.
- k = 1부터 N까지 반복하고, 그 안에서 i = 1부터 N까지, 다시 j = 1부터 N까지 반복하면서 다음 조건을 검사합니다.
cost[i][k] + cost[k][j] < cost[i][j]라면,
cost[i][j] := cost[i][k] + cost[k][j]로 갱신합니다. - 반복이 끝나면 행렬 cost[][]에는 각 노드 i에서 다른 모든 노드 j까지의 최단 비용이 저장됩니다.
플로이드-워셜 알고리즘은 단일 출발점이 아니라 모든 노드 쌍 간의 최단 경로를 한 번에 계산할 수 있는 것이 특징입니다.
세 가지 알고리즘 비교 요약
| 알고리즘 | 계산 방식 | 시간 복잡도 | 특징 |
|---|---|---|---|
| 벨만-포드 | 단일 출발점 | O(|V|·|E|) | 음의 가중치 간선 처리 가능, RIP의 기반 |
| 다익스트라 | 단일 출발점 | O((|V|+|E|) log |V|) | 음의 가중치 처리 불가, 속도가 빠름, OSPF의 기반 |
| 플로이드-워셜 | 모든 노드 쌍 | O(|V|³) | 모든 쌍 간 최단 경로를 한 번에 계산, 구현이 단순 |
네트워크 규모, 간선 가중치의 성격(음수 포함 여부), 필요한 결과(단일 출발점 또는 전체 쌍)에 따라 적합한 알고리즘이 달라집니다. 상황에 맞는 알고리즘을 선택하면 라우팅 효율성을 크게 높일 수 있습니다.