12.7 최단 경로 알고리즘의 기초

1. 최단 경로 문제의 개요

최단 경로 문제(shortest path problem)는 가중치 그래프에서 두 노드 사이의 가장 비용이 적은 경로를 찾는 문제이다. 가장 자연스럽고 광범위하게 활용되는 그래프 문제 중 하나이며, 도로 네트워크의 경로 안내, 통신 네트워크의 라우팅, 로봇의 경로 계획, 게임 AI의 캐릭터 이동 등 다양한 응용에서 핵심적이다. 본 절에서는 최단 경로 문제의 정의, 변형, 그리고 주요 알고리즘의 기초를 다룬다.

2. 최단 경로의 정의

2.1 경로의 비용

가중치 그래프 $G = (V, E, w)$ 에서 경로 $P = v_0, v_1, \ldots, v_k$ 의 비용(또는 길이)은 경로 위의 모든 엣지 가중치의 합이다.

$w(P) = \sum_{i=0}^{k-1}w(v_i, v_{i+1})$

2.2 최단 경로

두 노드 $s$ 와 $t$ 사이의 최단 경로는 모든 가능한 경로 중 비용이 가장 작은 경로이다.

$\delta(s, t) = \min\{w(P) : P \text{ is a path from } s \text{ to } t\}$

만약 $s$ 에서 $t$ 로의 경로가 존재하지 않으면 $\delta(s, t) = \infty$ 이다.

2.3 비가중치 그래프의 최단 경로

비가중치 그래프에서는 경로의 길이가 엣지의 수이다. 이 경우 BFS가 효율적으로 최단 경로를 찾는다.

3. 최단 경로 문제의 변형

3.1 단일 시작점 최단 경로

단일 시작점 최단 경로(Single-Source Shortest Path, SSSP) 문제는 한 시작 노드에서 다른 모든 노드까지의 최단 경로를 찾는다.

대표 알고리즘: Dijkstra, Bellman-Ford

3.2 단일 목표점 최단 경로

단일 목표점 최단 경로(Single-Destination Shortest Path) 문제는 모든 노드에서 한 목표 노드까지의 최단 경로를 찾는다. 그래프의 엣지를 뒤집고 SSSP를 적용하면 풀린다.

3.3 단일 쌍 최단 경로

단일 쌍 최단 경로(Single-Pair Shortest Path) 문제는 두 특정 노드 사이의 최단 경로를 찾는다. 일반적으로 SSSP의 특수한 경우로 풀린다.

대표 알고리즘: A*

3.4 모든 쌍 최단 경로

모든 쌍 최단 경로(All-Pairs Shortest Path, APSP) 문제는 모든 노드 쌍 사이의 최단 경로를 찾는다.

대표 알고리즘: Floyd-Warshall, Johnson

4. 최단 경로의 성질

4.1 부분 경로의 최적성

최단 경로의 부분 경로도 최단 경로이다. 즉, $P = v_0, v_1, \ldots, v_k$ 가 $v_0$ 에서 $v_k$ 로의 최단 경로이면, $P_{ij} = v_i, v_{i+1}, \ldots, v_j$ (여기서 $0 \leq i \leq j \leq k$ )는 $v_i$ 에서 $v_j$ 로의 최단 경로이다.

이 성질은 최단 경로 알고리즘 설계의 핵심이다.

4.2 삼각 부등식

최단 거리는 삼각 부등식을 만족한다.

$\delta(u, v) \leq \delta(u, w) + \delta(w, v)$

이는 최단 경로의 일관성을 보장한다.

4.3 이완(Relaxation)

최단 경로 알고리즘의 핵심 연산은 이완이다. 엣지 $(u, v)$ 의 이완은 다음과 같이 정의된다.

RELAX(u, v, w):
    if v.distance > u.distance + w(u, v):
        v.distance = u.distance + w(u, v)
        v.parent = u

이완은 현재 알려진 거리보다 더 짧은 경로가 발견되면 거리를 갱신한다.

5. 음수 가중치

5.1 음수 가중치 엣지

가중치가 음수인 엣지가 있을 수 있다. 예를 들어 거리 절약, 보상 등을 표현할 때이다. 음수 가중치는 일부 알고리즘(Dijkstra)을 사용할 수 없게 만든다.

5.2 음수 사이클

음수 사이클(negative cycle)은 가중치 합이 음수인 사이클이다. 음수 사이클이 있으면 그 사이클을 무한히 돌수록 비용이 줄어들므로, 최단 경로가 정의되지 않는다.

5.3 처리

Dijkstra: 음수 가중치를 처리할 수 없다.
Bellman-Ford: 음수 가중치를 처리할 수 있고, 음수 사이클을 검출할 수 있다.
Johnson: 음수 가중치를 양수로 변환한 후 Dijkstra를 적용한다.

6. Dijkstra 알고리즘

6.1 개요

Dijkstra 알고리즘은 음수 가중치가 없는 그래프에서 SSSP 문제를 푸는 표준 알고리즘이다. 1959년 에드스거 데이크스트라(Edsger Dijkstra)가 제안하였다.

6.2 기본 아이디어

Dijkstra 알고리즘은 그리디 방식이다. 시작 노드에서 출발하여 가장 가까운 미방문 노드를 차례로 처리한다. 각 노드를 처리할 때 그 이웃을 이완한다.

6.3 알고리즘

Dijkstra(G, s):
    for each node v in G:
        v.distance = ∞
        v.parent = None
    s.distance = 0
    
    Q = priority queue with all nodes
    while Q is not empty:
        u = Q.extract_min()
        for each neighbor v of u:
            if v in Q and v.distance > u.distance + w(u, v):
                v.distance = u.distance + w(u, v)
                v.parent = u
                Q.decrease_key(v, v.distance)

6.4 시간 복잡도

Dijkstra 알고리즘의 시간 복잡도는 우선순위 큐의 구현에 의존한다.

우선순위 큐	시간 복잡도
배열	$O(\vert V\vert^2)$
이진 힙	$O((\vert V\vert + \vert E\vert)\log\vert V\vert)$
피보나치 힙	$O(\vert V\vert\log\vert V\vert + \vert E\vert)$

이진 힙이 일반적으로 사용된다.

6.5 정확성

Dijkstra 알고리즘의 정확성은 그리디 선택이 최적임을 보임으로써 증명된다. 가장 가까운 미방문 노드를 처리하는 것이 항상 안전하다.

7. Bellman-Ford 알고리즘

7.1 개요

Bellman-Ford 알고리즘은 음수 가중치가 있는 그래프에서도 SSSP 문제를 풀 수 있다. 1958년 리차드 벨만(Richard Bellman)과 라이언 포드(Lester Ford)가 독립적으로 제안하였다.

7.2 알고리즘

Bellman_Ford(G, s):
    for each node v in G:
        v.distance = ∞
        v.parent = None
    s.distance = 0
    
    for i = 1 to |V| - 1:
        for each edge (u, v) in E:
            if v.distance > u.distance + w(u, v):
                v.distance = u.distance + w(u, v)
                v.parent = u
    
    // 음수 사이클 검사
    for each edge (u, v) in E:
        if v.distance > u.distance + w(u, v):
            return "Negative cycle exists"
    
    return distances

7.3 시간 복잡도

Bellman-Ford의 시간 복잡도는 $O(|V| \cdot |E|)$ 이다. Dijkstra보다 느리지만 음수 가중치를 처리할 수 있다.

7.4 음수 사이클 검출

Bellman-Ford는 음수 사이클을 검출할 수 있다. $|V| - 1$ 번의 이완 후에도 거리가 갱신되면 음수 사이클이 존재한다.

8. A* 알고리즘

8.1 개요

A* 알고리즘은 단일 쌍 최단 경로 문제를 위한 휴리스틱 기반 알고리즘이다. 1968년 페터 하트(Peter Hart), 닐스 닐슨(Nils Nilsson), 베르트람 라파엘(Bertram Raphael)이 제안하였다.

8.2 평가 함수

A* 알고리즘은 각 노드에 대해 평가 함수 $f(v)$ 를 정의한다.

$f(v) = g(v) + h(v)$

여기서

$g(v)$ : 시작 노드에서 $v$ 까지의 알려진 최단 거리
$h(v)$ : $v$ 에서 목표 노드까지의 추정 거리(휴리스틱)

8.3 알고리즘

A_star(G, s, t, h):
    open = priority queue
    s.g = 0
    s.f = h(s)
    open.add(s)
    closed = empty set
    
    while open is not empty:
        u = open.extract_min()
        if u == t:
            return reconstruct_path(u)
        closed.add(u)
        
        for each neighbor v of u:
            if v in closed:
                continue
            tentative_g = u.g + w(u, v)
            if v not in open or tentative_g < v.g:
                v.parent = u
                v.g = tentative_g
                v.f = v.g + h(v)
                if v not in open:
                    open.add(v)
    
    return "No path"

8.4 휴리스틱

휴리스틱 함수 $h$ 는 다음의 성질을 가져야 한다.

수용성(admissibility): $h(v) \leq h^*(v)$ , 여기서 $h^*(v)$ 는 실제 최단 거리이다. 수용성이 있으면 A*는 최적 해를 보장한다.
일관성(consistency): $h(u) \leq w(u, v) + h(v)$ , 모든 엣지 $(u, v)$ 에 대해. 일관성이 있으면 노드가 한 번만 처리된다.

8.5 일반적 휴리스틱

격자 그래프에서 자주 사용되는 휴리스틱은 다음과 같다.

맨해튼 거리: $h(v) = |v_x - t_x| + |v_y - t_y|$ (4방향 격자)
유클리드 거리: $h(v) = \sqrt{(v_x - t_x)^2 + (v_y - t_y)^2}$ (8방향 격자)
체비셰프 거리: $h(v) = \max(|v_x - t_x|, |v_y - t_y|)$

8.6 성능

A*는 좋은 휴리스틱이 있으면 Dijkstra보다 훨씬 효율적이다. 휴리스틱이 좋을수록 탐색 공간이 줄어든다.

9. Floyd-Warshall 알고리즘

9.1 개요

Floyd-Warshall 알고리즘은 모든 쌍 최단 경로 문제를 푸는 동적 프로그래밍 알고리즘이다. 1962년 로버트 플로이드(Robert Floyd)가 제안하였다.

9.2 알고리즘

Floyd_Warshall(G):
    n = |V|
    D = adjacency matrix of G
    
    for k = 1 to n:
        for i = 1 to n:
            for j = 1 to n:
                if D[i][k] + D[k][j] < D[i][j]:
                    D[i][j] = D[i][k] + D[k][j]
    
    return D

9.3 시간 복잡도

Floyd-Warshall의 시간 복잡도는 $O(|V|^3)$ 이다. 모든 쌍의 최단 경로를 한 번에 계산한다.

9.4 음수 가중치

Floyd-Warshall은 음수 가중치를 처리할 수 있지만, 음수 사이클이 있으면 정확한 결과를 보장하지 않는다.

10. Johnson 알고리즘

10.1 개요

Johnson 알고리즘은 모든 쌍 최단 경로를 위한 효율적인 알고리즘이다. 음수 가중치를 다룰 수 있다.

10.2 아이디어

Johnson 알고리즘은 음수 가중치를 양수로 변환한 후, 각 노드에서 Dijkstra를 적용한다. 변환은 Bellman-Ford로 계산된 가중 함수를 사용한다.

10.3 시간 복잡도

Johnson의 시간 복잡도는 $O(|V|^2\log|V| + |V||E|)$ 이다. 희소 그래프에서 Floyd-Warshall보다 효율적이다.

11. 알고리즘의 선택

11.1 그래프의 크기

크기	권장 알고리즘
작음	무엇이든
중간 (희소)	Dijkstra
중간 (밀집)	Floyd-Warshall
큼	A* (목표 노드 알려진 경우)

11.2 가중치의 종류

양수: Dijkstra
음수 가능: Bellman-Ford (단일 시작점), Johnson (모든 쌍)
비가중치: BFS

11.3 응용에 따른 선택

단일 시작점에서 모든 노드: Dijkstra
두 특정 노드: A* (좋은 휴리스틱이 있는 경우)
모든 쌍: Floyd-Warshall 또는 Johnson
동적 그래프: 증분 알고리즘

12. 응용

12.1 도로 네트워크

GPS 내비게이션과 지도 서비스에서 최단 경로 알고리즘이 핵심이다. 도로 네트워크는 매우 큰 그래프이며, 효율적인 알고리즘이 필요하다.

12.2 인터넷 라우팅

인터넷의 라우터는 최단 경로 알고리즘을 사용하여 패킷의 경로를 결정한다. OSPF, RIP 등이 대표적이다.

12.3 게임 AI

게임에서 캐릭터의 이동 경로 계산에 A*가 표준이다. 격자 기반 게임 환경에 효과적이다.

12.4 컴퓨터 네트워크

컴퓨터 네트워크의 라우팅, 트래픽 엔지니어링 등에 최단 경로 알고리즘이 사용된다.

13. 로봇공학에서의 응용

13.1 모바일 로봇의 경로 계획

모바일 로봇이 환경에서 목표 위치까지 이동할 때 최단 경로 알고리즘이 사용된다. 격자 기반 환경에서 A*가 일반적이다.

13.2 매니퓰레이터의 운동 계획

매니퓰레이터의 구성 공간에서 시작 자세에서 목표 자세까지의 경로를 찾는 데 최단 경로 알고리즘이 활용된다. 고차원이지만 샘플링 후 그래프 알고리즘이 적용된다.

13.3 자율 주행

자율 주행 차량의 경로 계획은 도로 네트워크에서 최단 경로 문제이다. 도착 시간, 안전성, 도로 상황 등을 가중치로 결합한다.

13.4 다중 로봇 경로 계획

다중 로봇이 협력하여 경로를 계획할 때 충돌 회피와 효율성을 동시에 고려한다.

13.5 SLAM의 회로 폐쇄

SLAM에서 회로 폐쇄 후의 최적화는 그래프 위의 비선형 최소제곱 문제이다. 최단 경로 알고리즘은 직접 사용되지 않지만, 그래프 구조 분석에 활용된다.

14. 응용 예시: 자율 주행 차량의 경로 계획

자율 주행 차량이 출발지에서 목적지까지 이동할 때 도로 네트워크의 최단 경로를 찾는다. Dijkstra 또는 A*가 사용된다.

def navigate(road_network, start, destination):
    return a_star(road_network, start, destination, heuristic=euclidean_distance)

14.1 시간 최적화

거리 최소화 외에 시간 최소화를 목적으로 할 수 있다. 가중치가 거리/속도이다.

14.2 동적 정보

교통 상황이 실시간으로 변하므로, 동적 가중치를 사용하는 알고리즘이 필요하다.

15. 응용 예시: 청소 로봇의 경로 계획

청소 로봇이 방을 효율적으로 청소하기 위한 경로를 계획한다. 격자로 분할된 환경에서 BFS, Dijkstra, A* 등이 사용된다.

16. 응용 예시: 매니퓰레이터의 운동 계획

매니퓰레이터의 구성 공간에서 시작 자세에서 목표 자세까지의 경로를 찾는다. 샘플링 기반 PRM(Probabilistic Roadmap)이 그래프를 구축한 후, Dijkstra나 A*로 경로를 찾는다.

17. 응용 예시: 드론의 비행 경로

드론이 장애물을 회피하면서 목표 위치로 비행할 때 3차원 격자에서 A* 등이 사용된다.

18. 응용 예시: 다중 로봇 협조

여러 로봇이 동시에 경로를 계획할 때 충돌 회피를 고려한다. CBS(Conflict-Based Search) 등의 알고리즘이 활용된다.

19. 알고리즘의 성능 비교

알고리즘	시간 복잡도	음수 가중치	응용
BFS	$O(\vert V\vert + \vert E\vert)$	비가중치만	비가중치 SSSP
Dijkstra	$O((\vert V\vert + \vert E\vert)\log\vert V\vert)$	불가	양수 SSSP
Bellman-Ford	$O(\vert V\vert\vert E\vert)$	가능	음수 SSSP
A*	휴리스틱 의존	불가	단일 쌍
Floyd-Warshall	$O(\vert V\vert^3)$	가능	모든 쌍
Johnson	$O(\vert V\vert^2\log\vert V\vert + \vert V\vert\vert E\vert)$	가능	모든 쌍 (희소)

20. 라이브러리 지원

20.1 NetworkX

import networkx as nx

G = nx.Graph()
G.add_weighted_edges_from([(1, 2, 0.5), (1, 3, 1.2), (2, 4, 1.5)])

# Dijkstra
distances = nx.single_source_dijkstra_path_length(G, source=1)
path = nx.dijkstra_path(G, source=1, target=4)

# A*
def heuristic(u, v):
    return 0  # 예시
path = nx.astar_path(G, source=1, target=4, heuristic=heuristic)

# Bellman-Ford
distances = nx.single_source_bellman_ford_path_length(G, source=1)

# Floyd-Warshall
distances = nx.floyd_warshall(G)

20.2 다른 라이브러리

igraph
Boost Graph Library
Google OR-Tools

21. 학습의 가치

최단 경로 알고리즘의 기초를 이해하는 것은 다음과 같은 이점을 제공한다.

가장 자주 사용되는 그래프 알고리즘의 원리를 이해한다.
로봇 경로 계획의 기본 도구를 익힌다.
다양한 응용에서 적절한 알고리즘을 선택할 수 있다.
알고리즘 설계의 핵심 기법(그리디, 동적 프로그래밍, 휴리스틱)을 학습한다.

22. 학습 권장사항

22.1 직접 구현

각 알고리즘을 직접 구현해 보는 것이 가장 효과적이다. Dijkstra와 A*는 특히 중요하다.

22.2 시각화

알고리즘의 단계별 동작을 시각화하면 이해가 깊어진다.

22.3 응용 학습

격자 환경의 경로 계획, 도로 네트워크의 최단 경로 등 실제 응용에 적용해 본다.

23. 본 절의 의의

본 절은 최단 경로 알고리즘의 기초를 다루었다. 이는 로봇공학의 다양한 영역에서 핵심적으로 활용되는 알고리즘이며, 후속 절에서 더 자세히 다룰 Dijkstra와 A* 알고리즘의 기반이 된다.

24. 참고 문헌

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
Dijkstra, E. W. (1959). “A note on two problems in connexion with graphs.” Numerische Mathematik, 1(1), 269–271.
Bellman, R. (1958). “On a routing problem.” Quarterly of Applied Mathematics, 16(1), 87–90.
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). “A formal basis for the heuristic determination of minimum cost paths.” IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.
LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press.
Floyd, R. W. (1962). “Algorithm 97: Shortest path.” Communications of the ACM, 5(6), 345.

version: 1.0