2026-06-01 TIL (68일차)

[TIL] 알고리즘: 최단 경로 알고리즘 (Shortest Path)

참고 영상: 동빈나 - (이코테 2021 강의 몰아보기) 7. 최단 경로 알고리즘

오늘은 그래프 상에서 가장 짧은 경로를 찾는 ‘최단 경로 알고리즘’에 대해 학습했습니다. 코딩 테스트에서 자주 등장하는 두 가지 핵심 알고리즘인 다익스트라(Dijkstra)와 플로이드 워셜(Floyd-Warshall)의 개념, 동작 원리, 시간 복잡도 및 구현 방법을 정리했습니다.

---

1. 최단 경로 알고리즘 개요

최단 경로 문제는 한 지점에서 다른 지점까지 가장 짧게 도달하는 방법을 찾는 문제입니다.

• 노드(Node): 도시, 마을, 국가 등 각 지점을 의미합니다.
• 간선(Edge): 지점 간 연결된 도로, 통로 등을 의미하며, 방향성과 비용(거리, 시간)을 가집니다.

---

2. 다익스트라 (Dijkstra) 최단 경로 알고리즘

특정한 하나의 출발 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘입니다.

특징

• 음의 간선이 없을 때만 정상 동작합니다. (현실의 도로는 음수가 없으므로 실제 길 찾기에 유용)
• 그리디(Greedy) 알고리즘 기반: 매 상황에서 “가장 비용이 적은(가장 가까운) 노드”를 선택하여 과정을 반복합니다.
• 한 번 선택된 노드의 최단 거리는 확정되어 더 이상 바뀌지 않습니다.

동작 과정

1. 출발 노드를 설정하고, 최단 거리 테이블을 초기화합니다. (출발 노드=0, 나머지=무한(Infinity))
2. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택합니다.
3. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여, 기존의 최단 거리보다 작으면 최단 거리 테이블을 갱신합니다.
4. 모든 노드를 방문할 때까지 2~3번 과정을 반복합니다.

시간 복잡도와 개선 (우선순위 큐 활용)

• 단순 구현 (선형 탐색): O(V^2) (V는 노드의 개수). 노드가 5,000개 이할 때 적합.
• 개선된 구현 (우선순위 큐/힙 사용): O(E log V) (E는 간선의 개수). 노드가 10,000개 이상일 때 필수.
  • 최소 힙(Min Heap)을 사용하여 가장 가까운 노드를 탐색하는 데 걸리는 시간을 O(log V)로 단축합니다.
  • 이미 방문 처리된(테이블 값보다 큰) 꺼낸 거리는 무시(continue)하여 속도를 극대화합니다.

3. 플로이드 워셜 (Floyd-Warshall) 알고리즘

모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 구하는 알고리즘입니다.

특징

• 다익스트라와 달리 2차원 테이블에 최단 거리 정보를 저장합니다.
• 다이나믹 프로그래밍(DP) 알고리즘 기반: 점화식에 맞게 테이블을 갱신합니다.
• 구현이 매우 간단하지만, 시간 복잡도가 크기 때문에 노드의 개수가 적을 때(일반적으로 500개 이하)만 사용 가능합니다.

동작 과정 및 점화식

• 점화식: D_ab = min(D_ab, D_ak + D_kb)
• “A에서 B로 가는 거리”와 “A에서 K를 거쳐 B로 가는 거리”를 비교하여 더 작은 값으로 갱신합니다.
• 노드 개수만큼의 단계를 반복하며, 각 단계마다 특정 노드(K)를 거쳐 가는 모든 경우(A->B)를 확인합니다.

시간 복잡도

• O(N^3)
• 3중 반복문을 사용하기 때문에 노드의 개수(N)가 커지면 기하급수적으로 연산량이 증가합니다.

---

요약 및 적용 기준

알고리즘	목적	시간 복잡도	사용 조건 / 특징
다익스트라 (우선순위 큐)	한 노드 👉 다른 모든 노드	O(E log V)	노드와 간선이 많을 때 (노드 1만 개 이상도 거뜬). 그리디 기반.
플로이드 워셜	모든 노드 👉 다른 모든 노드	O(V^3)	노드 개수가 적을 때 (보통 500개 이하). DP 기반, 코드가 매우 간결.

문제를 접했을 때, 출발지가 하나인지 모든 노드인지 파악하고 N(노드의 개수)의 크기를 확인하여 다익스트라를 쓸지, 플로이드 워셜을 쓸지 결정하는 것이 중요합니다!