최단경로 알고리즘

왜 배우는가: 최단경로 알고리즘은 네비게이션, 라우팅, 물류, 게임 AI 등 실무 경로 탐색의 기반이다. 다익스트라·벨만-포드·플로이드-워셜·A*의 차이를 구분하는 문제가 정보관리기술사 4교시에서 반복 출제되므로 개념과 적용 조건을 함께 정리해야 한다.

출제 이력: 제123회 4교시 6번, 제98회 4교시 1번

1. 한 줄 정의와 핵심 키워드

최단경로 알고리즘은 가중치가 있는 그래프에서 출발 정점부터 목적 정점까지 간선 가중치 합이 최소인 경로를 찾는 알고리즘이다.

핵심 키워드

• 최단경로(Shortest Path): 두 정점 사이 간선 가중치 합이 최소인 경로
• 가중 그래프(Weighted Graph): 간선마다 비용·거리·시간 값을 가진 그래프
• 다익스트라(Dijkstra) 알고리즘: 음이 아닌 가중치에서 단일 출발 최단경로를 구하는 그리디 방법
• 벨만-포드(Bellman-Ford) 알고리즘: 음의 가중치를 허용하고 음의 사이클을 검출하는 방법
• 플로이드-워셜(Floyd-Warshall) 알고리즘: 모든 정점 쌍의 최단경로를 구하는 동적계획법
• A* 알고리즘: 휴리스틱 추정값으로 목표 방향을 우선 탐색하는 방법
• 휴리스틱 함수(Heuristic Function): 현재 정점에서 목표까지 남은 거리의 추정 함수

2. 개념 풀이

쉬운 말로 하면 지도 앱이 출발지에서 목적지까지 가장 짧은 길을 찾는 원리다. 각 교차로까지의 최소 비용을 조금씩 확정해 나가면서 목적지까지 도달한다.

정식 정의는 다음과 같다. 가중 그래프 G=(V,E)에서 간선 (u,v)의 가중치를 w(u,v)라 할 때, 출발 정점 s에서 정점 v까지의 최단거리 d(s,v)는 경로상 간선 가중치 합의 최솟값이다.

단일 출발 최단경로(Single-Source Shortest Path) 는 한 출발점에서 모든 정점까지 최단거리를 구하는 문제다. 모든 쌍 최단경로(All-Pairs Shortest Path) 는 모든 정점 쌍의 거리를 구하는 문제다. 두 문제의 범위가 달라 알고리즘 선택 기준이 된다.

그리디(Greedy) 방식은 매 단계에서 지금 가장 가까운 미확정 정점을 확정한다. 다익스트라가 여기에 해당한다. 동적계획법(Dynamic Programming) 방식은 중간 정점을 하나씩 허용하면서 작은 문제의 해를 쌓아 올린다. 플로이드-워셜이 여기에 해당한다.

휴리스틱 추정값 f(n)=g(n)+h(n) 은 출발점에서 정점 n까지 실제 비용 g(n)과 n에서 목표까지 추정 비용 h(n)의 합이다. h(n)이 실제 남은 거리를 넘지 않을 때 이를 허용적(admissible) 휴리스틱이라 한다.

3. 등장 배경과 필요성

초기 경로 탐색은 모든 경로를 나열하는 방식이어서 정점 수가 늘면 계산량이 지수적으로 커졌다. 그래프 이론에서 간선 가중치를 체계적으로 다루는 방법이 필요해지면서 다익스트라 방식이 정립되었다.

통신망 라우팅에서는 패킷이 최소 비용 경로로 전달되어야 한다. 이때 링크 상태 기반 프로토콜이 다익스트라를 사용하는 이유가 여기에 있다. 교통·물류에서도 거리와 시간을 가중치로 두고 최적 경로를 찾는 수요가 크다.

게임 AI와 로봇 경로 계획에서는 맵이 크고 실시간 응답이 필요하다. 모든 방향을 균등하게 탐색하는 방식은 느리므로 목표 방향을 우선하는 A*가 등장했다. 1968년 하트(Hart), 닐슨(Nilsson), 라펠(Raphael)이 A 알고리즘을 발표했고, 적절한 휴리스틱에서 최적성이 보장되어 A*로 불린다.

음의 가중치가 들어오는 문제에서는 다익스트라가 올바르지 않으므로 벨만-포드가 필요하다. 음의 사이클이 있으면 최단경로가 정의되지 않으므로 이를 검출하는 기능도 필요해졌다.

4. 구성요소·원리·절차

최단경로 알고리즘은 그래프 G=(V,E)에서 출발 정점에서 목적 정점까지 간선 가중치의 합이 최소인 경로를 찾는다. 구성요소는 정점(노드), 간선(엣지), 가중치, 그리고 거리 배열이나 우선순위 큐 같은 보조 자료구조다. 네 가지 대표 알고리즘은 완화(relaxation) 연산을 공통으로 쓴다.

완화는 간선 (u, v)를 지날 때 비용이 줄면 갱신하는 연산이다.

$dist[v] \leftarrow \min(dist[v],\; dist[u] + w(u,v))$

여기서 dist[v]는 v까지 현재 찾은 최소 비용, w(u,v)는 간선 가중치다. 이 식을 반복하면 최단 거리가 확정된다. 원리는 최적 부분구조다. 최단 경로의 부분 경로도 최단이어야 한다는 성질이다. 다익스트라는 이 성질에 탐욕 선택을 더해 가장 가까운 미확정 정점을 한 번씩 확정한다. 벨만-포드는 간선 전체를 |V|-1번 완화해 경로 길이가 늘어나며 정답을 맞춘다. 플로이드-워셜은 중간 정점 k를 하나씩 허용하는 동적계획법으로 모든 쌍을 계산한다.

다익스트라 절차는 다음과 같다.

• 출발 정점 dist=0, 나머지 dist=∞로 초기화하고 우선순위 큐에 넣는다.
• 큐에서 dist가 최소인 정점 u를 꺼내 확정한다.
• u의 모든 인접 정점 v에 대해 완화 연산을 수행한다.
• 큐가 빌 때까지 2~3을 반복한다.

벨만-포드 절차는 다음과 같다.

• 모든 dist를 ∞, 출발점은 0으로 둔다.
• 모든 간선에 대해 완화를 |V|-1회 반복한다.
• 한 번 더 완화했을 때 갱신이 일어나면 음의 사이클이 존재한다고 판정한다.

A* 절차는 다익스트라와 같으나 우선순위를 f(v)=g(v)+h(v)로 정한다. g(v)는 출발점에서 v까지 실제 비용, h(v)는 v에서 목적지까지의 추정 비용이다. h(v)가 실제 잔여 비용을 넘지 않으면(admissible) 최단 경로가 보장된다.

다익스트라는 음수 가중치가 없을 때 정확하고, 벨만-포드는 음수 간선과 음의 사이클 검출이 가능하다.

플로이드-워셜 점화식은 다음과 같다.

$D_k[i][j] = \min(D_{k-1}[i][j],\; D_{k-1}[i][k] + D_{k-1}[k][j])$

여기서 D_k[i][j]는 정점 1~k만 중간에 허용했을 때 i에서 j까지 최단 거리다. 3중 반복문이므로 시간 복잡도는 O(|V|^3)이다.

5. 관련 법령·기준·표준

최단경로 알고리즘은 법령이 정한 기준이 아니라 알고리즘 표준과 학술 문헌으로 정의된다. 다음 표는 네 알고리즘의 기준 수치와 조건이다.

다익스트라의 기본 형태는 논문에서 제시되었다는 설명이 널리 알려져 있으나 세부 연혁은 확인이 필요하다.

수식과 관련해 A*의 admissible 조건은 다음과 같다. 모든 v에 대해 h(v) \le h^(v)여야 하며, h^(v)는 v에서 목적지까지 실제 최소 비용이다. 이 조건을 만족하면 최단 경로가 보장된다. 휴리스틱이 실제 잔여 비용을 과대평가하면 최단이 아닌 경로가 선택될 수 있다.

플로이드-워셜의 계산 기준은 정점 수 n에 대해 n^3 번의 완화다. 예를 들어 정점 100개이면 약 100만 번 연산이다. 계산 결과가 상식 범위인지 확인할 때는 한 번 확정된 거리가 이후에 증가하지 않는지 점검한다.

6. 유형과 비교

최단경로 알고리즘은 문제의 형태에 따라 단일 출발 방식과 모든 쌍 방식으로 나뉜다. 간선 가중치의 부호와 탐색 방식에 따라 알고리즘을 고른다. 아래 표는 4가지 대표 알고리즘을 같은 기준으로 비교한다.