최단 경로 알고리즘 편집하기

최단 경로 알고리즘(Shortest path algorithm, 最短經路算法)은 그래프 상에서 한 정점에서 다른 정점으로의 최단 경로를 계산하기 위한 알고리즘들을 통칭하는 개념이다.
==개요==
최단 경로 알고리즘은 컴퓨터 과학, 수학, 물류, 네트워크 등 다양한 분야에서 핵심적인 알고리즘으로 사용된다. 그래프는 정점(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를 찾는다.
==주요 알고리즘==
대표적인 최단 경로 알고리즘은 다음과 같다.
*[[다익스트라 알고리즘]]: 음의 가중치가 없는 그래프에서 단일 시작점 문제 해결. 시간 복잡도는 O((V+E)logV)
*[[벨만-포드 알고리즘]]: 음의 가중치가 있는 경우에도 동작 가능. 시간 복잡도는 O(VE)
*[[플로이드-워셜 알고리즘]]: 모든 정점 쌍 간 최단 경로 계산. 시간 복잡도는 O(V^3)
*[[A* 알고리즘]]: 휴리스틱 기반 탐색 알고리즘. 실시간 경로 탐색에 효과적
==예시==
다음 그래프에서 정점 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
==응용==
최단 경로 알고리즘은 다음과 같은 분야에 사용된다.
*내비게이션 및 지도 서비스에서 경로 최적화
*통신 네트워크에서 패킷 전달 경로 계산
*게임에서 캐릭터의 경로 탐색
*공급망 및 물류의 경로 최적화
==한계==
*음의 사이클이 존재할 경우 일부 알고리즘은 정상 동작하지 않음
*실시간 환경에서는 계산 지연 문제가 발생할 수 있음
*대규모 그래프에서는 계산량이 많아 성능 최적화가 필요함
==같이 보기==
*[[그래프 이론]]
*[[다익스트라 알고리즘]]
*[[벨만-포드 알고리즘]]
*[[플로이드-워셜 알고리즘]]
*[[A* 알고리즘]]
==참고 문헌==
*Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). *Introduction to Algorithms* (3rd ed.). MIT Press.
==각주==
[[분류:알고리즘]]
[[분류:그래프 이론]]