최단 경로 알고리즘

최단 경로 알고리즘(Shortest path algorithm, 最短經路算法)은 그래프 상에서 한 정점에서 다른 정점으로의 최단 경로를 계산하기 위한 알고리즘들을 통칭하는 개념이다.

1 개요

최단 경로 알고리즘은 컴퓨터 과학, 수학, 물류, 네트워크 등 다양한 분야에서 핵심적인 알고리즘으로 사용된다. 그래프는 정점(vertex)과 간선(edge)으로 이루어지며, 각 간선에는 비용 또는 거리 등의 가중치가 할당된다. 이 알고리즘들은 이러한 가중치를 고려하여 특정 정점 간의 최소 비용 경로를 효율적으로 계산한다.

문제 유형은 다음과 같이 구분된다.

• 단일 시작점에서 모든 정점까지의 최단 경로 (Single-source shortest path)
• 모든 정점 쌍 사이의 최단 경로 (All-pairs shortest path)
• 특정 두 정점 사이의 최단 경로 (Single-pair shortest path)

수학적으로 그래프 G = (V, E)가 주어졌을 때, 각 간선 (u, v) ∈ E에는 가중치 w(u, v)가 정의된다. 정점 s에서 정점 t로 가는 경로 P = (s = v0, v1, ..., vk = t)가 있을 때, 경로 P의 총 가중치는 다음과 같이 정의된다.

w(P) = w(v0, v1) + w(v1, v2) + ... + w(vk-1, vk)

최단 경로 알고리즘은 이 w(P)를 최소화하는 경로 P를 찾는다.

2 주요 알고리즘

대표적인 최단 경로 알고리즘은 다음과 같다.

• 다익스트라 알고리즘: 음의 가중치가 없는 그래프에서 단일 시작점 문제 해결. 시간 복잡도는 O((V+E)logV)
• 벨만-포드 알고리즘: 음의 가중치가 있는 경우에도 동작 가능. 시간 복잡도는 O(VE)
• 플로이드-워셜 알고리즘: 모든 정점 쌍 간 최단 경로 계산. 시간 복잡도는 O(V^3)
• A* 알고리즘: 휴리스틱 기반 탐색 알고리즘. 실시간 경로 탐색에 효과적

3 예시

다음 그래프에서 정점 A에서 C까지의 최단 경로를 계산한다.

그래프:

A --(3)--> B --(1)--> C
 \                   ^
  \(5)--------------/

가능한 경로:

• A → B → C: 거리 3 + 1 = 4
• A → C: 거리 5

최단 경로는 A → B → C이며, 총 거리는 4이다.

수학적으로:

• w(A → B → C) = w(A, B) + w(B, C) = 3 + 1 = 4
• w(A → C) = 5

min{w(A → B → C), w(A → C)} = min{4, 5} = 4

4 응용

최단 경로 알고리즘은 다음과 같은 분야에 사용된다.

• 내비게이션 및 지도 서비스에서 경로 최적화
• 통신 네트워크에서 패킷 전달 경로 계산
• 게임에서 캐릭터의 경로 탐색
• 공급망 및 물류의 경로 최적화

5 한계

• 음의 사이클이 존재할 경우 일부 알고리즘은 정상 동작하지 않음
• 실시간 환경에서는 계산 지연 문제가 발생할 수 있음
• 대규모 그래프에서는 계산량이 많아 성능 최적화가 필요함

6 같이 보기

• 그래프 이론
• 다익스트라 알고리즘
• 벨만-포드 알고리즘
• 플로이드-워셜 알고리즘
• A* 알고리즘

7 참고 문헌

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). *Introduction to Algorithms* (3rd ed.). MIT Press.