• algorithm
  • graph

최단 경로 알고리즘: BFS, 다익스트라, 벨만-포드, 플로이드-워셜, A*

그래프 최단 경로 알고리즘 다섯 가지의 동작 원리와 시간 복잡도, 음수 간선과 음수 사이클에 따른 선택 기준을 정리한다.

Manx5분 읽기
시리즈 · 자료구조 · 알고리즘10 / 13
  1. 시간 복잡도와 공간 복잡도
  2. 재귀 함수와 꼬리 재귀 최적화
  3. 연결 리스트(Linked List)
  4. 스택과 큐: 원형 큐 구현과 덱
  5. 해시 테이블: 해시 함수와 충돌 처리
  6. 트리와 이진 탐색 트리
  7. 힙(Heap)과 우선순위 큐
  8. 균형 이진 탐색 트리: AVL, Red-Black, B-Tree
  9. 그래프: 인접 행렬과 인접 리스트
  10. 최단 경로 알고리즘: BFS, 다익스트라, 벨만-포드, 플로이드-워셜, A*
  11. 최소 신장 트리(MST): Kruskal, Prim, Union-Find
  12. 정렬 알고리즘: 퀵·병합·기수 정렬부터 Timsort까지
  13. Thread-Safe 자료구조: Python GIL과 Java ConcurrentHashMap

한눈에 보기

V는 정점의 수, E는 간선의 수이다.

알고리즘 구하는 것 시간 복잡도 음수 간선
BFS 한 정점 → 모든 정점 (가중치 없음) O(V + E) -
다익스트라 한 정점 → 모든 정점 O(E log V) 불가
벨만-포드 한 정점 → 모든 정점 O(VE) 가능, 음수 사이클 판별
플로이드-워셜 모든 정점 → 모든 정점 O(V³) 가능 (음수 사이클은 불가)
A* 한 정점 → 한 정점 휴리스틱에 따라 다름 불가

시작 노드에서 가까운 노드부터 탐색한다. 거리가 1인 모든 노드를 방문한 뒤 거리가 2인 모든 노드를 방문하는 순서이다.

  • 거리 순으로 탐색하므로, 처음 목적지에 도달한 순간이 최단 거리이다.
  • 간선마다 비용이 같은(가중치가 없는) 그래프에서만 최단 거리를 보장한다.
  • 시간 복잡도: O(V + E). 모든 노드와 간선을 한 번씩 방문하기 때문이다.

다익스트라(Dijkstra)

최단 거리 테이블을 유지하면서, 아직 방문하지 않은 노드 중 비용이 가장 낮은 노드를 선택해 그 노드를 거쳐 가는 경로로 테이블을 갱신하는 알고리즘이다.

  • “가장 낮은 비용의 노드”를 빠르게 꺼내기 위해 우선순위 큐(힙)으로 구현한다.
  • 시간 복잡도: O(E log V)

음수 가중치가 있으면 쓸 수 없다

다익스트라는 한 번 방문해 확정한 노드의 거리가 이후에 더 줄어들지 않는다고 가정한다. 음수 간선이 있으면 이 가정이 깨져 올바른 결과를 보장하지 못한다.

음수 사이클이 있는 경우는 더 근본적인 문제가 있다. 사이클을 돌수록 비용이 계속 줄어들기 때문에 최단 거리 자체를 정의할 수 없다.

음수 가중치 간선과, 돌수록 비용이 줄어드는 음수 사이클(e와 f 사이)이 포함된 방향 그래프

힙을 사용하지 않고 구현한다면

매번 방문하지 않은 노드 전체를 훑어 가장 비용이 낮은 노드를 찾아야 하므로 O(V²)이 된다.

벨만-포드(Bellman-Ford)

다익스트라와 달리 음수 간선이 있어도 최단 거리를 구할 수 있고, 음수 사이클의 존재도 판별할 수 있다. 매 단계에서 모든 간선을 확인하기 때문이다.

  1. 모든 간선에 대해, 기존에 저장된 거리보다 현재 노드를 거쳐 인접 노드에 도달하는 거리가 더 짧으면 값을 갱신한다.
  2. 이 과정을 V - 1번 반복한다.
  3. 마지막으로 한 번 더 수행한다. 이때도 갱신되는 값이 있다면 음수 사이클이 존재하는 것이므로 최단 거리가 없다고 판단한다.
  • 시간 복잡도: O(VE). 매 반복에서 모든 간선을 확인하므로 다익스트라보다 느리다.

플로이드-워셜(Floyd-Warshall)

모든 노드에서 모든 노드까지의 최단 거리를 구한다.

  • 각 노드를 차례로 중간 노드로 선정하고, 그 노드를 거쳐 가는 경로가 더 짧으면 값을 갱신한다.
  • 시간 복잡도: O(V³)

A* 알고리즘

다익스트라는 시작 노드만 지정해 다른 모든 노드까지의 최단 경로를 구한다. A*는 시작 노드와 목적지 노드를 분명하게 지정해 두 노드 사이의 최단 경로를 구한다.

f(n) = g(n) + h(n)
  • G: 시작 노드에서 해당 노드까지 실제로 든 비용
  • H: 해당 노드에서 목적지까지의 휴리스틱 추정값 (좌표 차이나 직선 거리 등)
  • Parent Node: 해당 노드에 도달하기 위해 직전에 거친 노드

h(n) = 0이면 다익스트라와 동일하게 동작한다.

동작 과정

후보 노드를 담는 O(Open List)와 확정된 노드를 담는 C(Close List)를 사용한다.

  1. 시작 노드를 C에 넣고, 연결된 노드들을 F, G, H, Parent Node와 함께 O에 담는다.
  2. O에서 F가 가장 작은 노드를 꺼내 C에 추가한다.
  3. 그 노드와 연결된 노드들을 O에 담는다. 이미 O에 있는 노드는 더 작은 값으로 갱신한다.
  4. 목적지 노드가 C에 담길 때까지 2~3을 반복한다.

시작 노드 0을 C에 넣고 인접한 노드 1과 3의 F, G, H 값을 O에 담은 A* 초기 상태

목적지 노드가 C에 담기면, Parent Node를 거꾸로 타고 올라간 경로가 최단 경로가 된다.

목적지 노드 6이 C에 담긴 뒤 Parent Node를 따라 0 → 1 → 2 → 6 경로가 구해진 A* 종료 상태

성능

성능은 휴리스틱 함수를 어떻게 설정하느냐에 따라 달라진다. 추정이 실제 남은 비용에 가까울수록 불필요한 노드를 덜 탐색한다. 다만 휴리스틱이 실제 비용을 과대평가하면 최단 경로를 보장하지 못한다.

대표적인 휴리스틱 함수로 맨해튼 거리와 유클리드 거리가 있다.

어떤 알고리즘을 써야 할까

  • 가중치가 없다 → BFS
  • 한 정점에서 다른 모든 정점까지의 최단 거리가 필요하다 → 다익스트라
  • 출발 노드와 도착 노드가 정해져 있다 → A*
  • 음수 간선이 있거나 음수 사이클 여부를 판별해야 한다 → 벨만-포드
  • 모든 정점 쌍의 최단 거리가 필요하다 → 플로이드-워셜

정점이 N개, 간선이 N³개라면?

  • BFS: O(N + N³) = O(N³)
  • 다익스트라: O(N³ log N)

트리에서 두 노드 사이의 최단 거리는 어떻게 구할까?

트리에서는 두 노드를 잇는 경로가 하나뿐이므로 LCA(최소 공통 조상) 알고리즘을 사용한다. 두 노드의 깊이를 먼저 맞춘 뒤, 동시에 위로 올라가며 처음 만나는 공통 조상을 찾는다. 두 노드에서 공통 조상까지의 거리를 더하면 최단 거리이다.