최단 경로 (Shortest Path)

2026년 6월 24일 · 수정 2026년 6월 24일 · 📖 약 4분 · 1,260자/단어 #algorithm #graph #shortest-path #bfs #dijkstra #bellman-ford #floyd-warshall

정의

최단 경로 (Shortest Path) 는 그래프 G = (V, E) 에서 시작 정점 s 에서 목표 정점 t 까지 가는 경로 중 가중치 합이 최소인 경로 를 찾는 문제. 단일 출발점 (Single Source), 모든 쌍 (All Pairs), 음수 가중치 유무, 가중치 범위, 노드 수 등에 따라 최적 알고리즘이 달라진다.

문제 상황과 동기

네트워크, 도로망, 게임 맵 등에서 가장 빠르거나 저렴한 경로 를 찾는다.

naive: 모든 경로를 탐색. 지수 개 경로 존재 가능, 폭발.
BFS: 간선 가중치 동일 (또는 0/1). O(V + E).
Dijkstra: 음수 간선 없음. O((V + E) log V) with min-heap.
Bellman-Ford: 음수 간선 가능, 음수 사이클 탐지. O(VE).
Floyd-Warshall: 모든 쌍 거리. O(V^3). V ≤ 400 정도.
0-1 BFS: 가중치 0 또는 1. O(V + E) deque.

핵심 통찰: relax 연산 dist[v] = min(dist[v], dist[u] + w(u, v)) 을 어떤 순서로 몇 번 하는가 가 알고리즘 본질.

시각화

알고리즘 선택 가이드

조건	알고리즘	복잡도	비고
가중치 없음 (또는 모두 1)	[[BFS	BFS]]	O(V + E)
가중치 0/1	0-1 BFS	O(V + E)	deque push_front/back
음수 간선 없음, 단일 출발점	Dijkstra	O((V + E) log V)	min-heap + relax
음수 간선 가능, 단일 출발점	Bellman-Ford	O(VE)	V-1 라운드 relax
음수 사이클 탐지	Bellman-Ford	O(VE)	V 번째 라운드에서 변화 체크
모든 쌍 거리	Floyd-Warshall	O(V^3)	V ≤ 400, DP 3중 루프
모든 쌍, V 작고 E 많음	V 번 Dijkstra	O(V(V + E) log V)	V^2 log V < V^3 when E ≈ V^2
최단 경로 트리	Dijkstra / BFS	-	parent 배열로 복원
k-th shortest path	Yen’s algorithm	-	k 번 Dijkstra 변형

핵심 아이디어

Relax 연산

relax(u, v, w):
    if dist[v] > dist[u] + w:
        dist[v] = dist[u] + w
        parent[v] = u

모든 최단 경로 알고리즘은 relax 를 여러 간선에 반복. 차이는 순서 와 반복 횟수.

BFS (가중치 1)

queue 로 너비 우선 탐색. 먼저 발견한 거리가 최단. O(V + E).

Dijkstra (음수 간선 없음)

greedy: 매번 dist[v] 가 최소인 v 를 확정하고 인접 간선 relax.

dist[v] 가 확정되면 다시 바뀌지 않음 (음수 간선 없으므로).
min-heap 으로 O((V + E) log V).
경로 복원: parent 배열.

invariant: 확정된 노드의 dist 는 정확한 최단 거리.

Bellman-Ford (음수 간선 가능)

V - 1 번 모든 간선 에 relax. V - 1 번 이내에 dist 가 수렴 (경로 길이 ≤ V - 1).

V 번째 라운드에서도 변화가 있으면 음수 사이클 존재.
실제로는 SPFA (queue + in-queue flag) 로 O(VE) 평균 개선.

Floyd-Warshall (모든 쌍)

DP: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for all k.

for k = 0..V-1:
    for i = 0..V-1:
        for j = 0..V-1:
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

음수 간선 가능, 음수 사이클은 dist[i][i] < 0 로 탐지.

구현

BFS (가중치 1)

// BFS, 가중치 1, 단일 출발점
#include <bits/stdc++.h>
using namespace std;
int main() {
  int V, E, s; cin >> V >> E >> s;
  vector<vector<int>> adj(V);
  for (int i = 0; i < E; i++) {
      int u, v; cin >> u >> v;
      adj[u].push_back(v);
  }
  vector<int> dist(V, -1);
  queue<int> q;
  dist[s] = 0; q.push(s);
  while (!q.empty()) {
      int u = q.front(); q.pop();
      for (int v : adj[u]) {
          if (dist[v] == -1) {
              dist[v] = dist[u] + 1;
              q.push(v);
          }
      }
  }
  for (int i = 0; i < V; i++)
      cout << dist[i] << (i == V - 1 ? "\n" : " ");
}

# BFS, collections.deque
from collections import deque
import sys
input = sys.stdin.readline

V, E, s = map(int, input().split())
adj = [[] for _ in range(V)]
for _ in range(E):
  u, v = map(int, input().split())
  adj[u].append(v)

dist = [-1] * V
q = deque([s])
dist[s] = 0
while q:
  u = q.popleft()
  for v in adj[u]:
      if dist[v] == -1:
          dist[v] = dist[u] + 1
          q.append(v)
print(' '.join(map(str, dist)))

stdin

결과

0 1 1 2

Dijkstra (음수 간선 없음)

// Dijkstra, priority_queue (min-heap)
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long, int> pli;
const long long INF = 1e18;
int main() {
  int V, E, s; cin >> V >> E >> s;
  vector<vector<pair<int, long long>>> adj(V);
  for (int i = 0; i < E; i++) {
      int u, v; long long w; cin >> u >> v >> w;
      adj[u].push_back({v, w});
  }
  vector<long long> dist(V, INF);
  priority_queue<pli, vector<pli>, greater<pli>> pq;
  dist[s] = 0; pq.push({0, s});
  while (!pq.empty()) {
      auto [d, u] = pq.top(); pq.pop();
      if (d > dist[u]) continue;
      for (auto [v, w] : adj[u]) {
          if (dist[v] > dist[u] + w) {
              dist[v] = dist[u] + w;
              pq.push({dist[v], v});
          }
      }
  }
  for (int i = 0; i < V; i++)
      cout << (dist[i] == INF ? -1 : dist[i]) << (i == V - 1 ? "\n" : " ");
}

# Dijkstra, heapq
import heapq
import sys
input = sys.stdin.readline
INF = float('inf')

V, E, s = map(int, input().split())
adj = [[] for _ in range(V)]
for _ in range(E):
  u, v, w = map(int, input().split())
  adj[u].append((v, w))

dist = [INF] * V
dist[s] = 0
pq = [(0, s)]
while pq:
  d, u = heapq.heappop(pq)
  if d > dist[u]: continue
  for v, w in adj[u]:
      if dist[v] > dist[u] + w:
          dist[v] = dist[u] + w
          heapq.heappush(pq, (dist[v], v))
print(' '.join(str(-1 if d == INF else d) for d in dist))

stdin

결과

0 2 3 4

Bellman-Ford (음수 간선 가능)

C++

// Bellman-Ford, 음수 사이클 탐지
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
struct Edge { int u, v; long long w; };
int main() {
  int V, E, s; cin >> V >> E >> s;
  vector<Edge> edges(E);
  for (auto& [u, v, w] : edges) cin >> u >> v >> w;
  vector<long long> dist(V, INF);
  dist[s] = 0;
  for (int i = 0; i < V - 1; i++)
      for (auto [u, v, w] : edges)
          if (dist[u] != INF && dist[v] > dist[u] + w)
              dist[v] = dist[u] + w;
  bool neg_cycle = false;
  for (auto [u, v, w] : edges)
      if (dist[u] != INF && dist[v] > dist[u] + w)
          neg_cycle = true;
  if (neg_cycle) cout << "NEGATIVE CYCLE\n";
  else for (int i = 0; i < V; i++)
      cout << (dist[i] == INF ? -1 : dist[i]) << (i == V - 1 ? "\n" : " ");
}

stdin

결과

0 2 3 4

Floyd-Warshall (모든 쌍)

// Floyd-Warshall, O(V^3)
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
int main() {
  int V, E; cin >> V >> E;
  vector<vector<long long>> dist(V, vector<long long>(V, INF));
  for (int i = 0; i < V; i++) dist[i][i] = 0;
  for (int i = 0; i < E; i++) {
      int u, v; long long w; cin >> u >> v >> w;
      dist[u][v] = min(dist[u][v], w);
  }
  for (int k = 0; k < V; k++)
      for (int i = 0; i < V; i++)
          for (int j = 0; j < V; j++)
              dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
  for (int i = 0; i < V; i++) {
      for (int j = 0; j < V; j++)
          cout << (dist[i][j] == INF ? -1 : dist[i][j]) << (j == V - 1 ? "\n" : " ");
  }
}

# Floyd-Warshall
import sys
input = sys.stdin.readline
INF = float('inf')

V, E = map(int, input().split())
dist = [[INF] * V for _ in range(V)]
for i in range(V): dist[i][i] = 0
for _ in range(E):
  u, v, w = map(int, input().split())
  dist[u][v] = min(dist[u][v], w)
for k in range(V):
  for i in range(V):
      for j in range(V):
          dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
for row in dist:
  print(' '.join(str(-1 if d == INF else d) for d in row))

stdin

결과

복잡도

알고리즘	시간	공간	음수 간선	음수 사이클 탐지
BFS	O(V + E)	O(V)	✗	✗
0-1 BFS	O(V + E)	O(V)	✗	✗
Dijkstra (heap)	O((V + E) log V)	O(V)	✗	✗
Bellman-Ford	O(VE)	O(V)	✓	✓
Floyd-Warshall	O(V^3)	O(V^2)	✓	✓ (diagonal)

변형 / 활용

경로 복원

parent 배열로 역추적.

while (t != s) {
    path.push_back(t);
    t = parent[t];
}
path.push_back(s);
reverse(path.begin(), path.end());

k번째 최단 경로

Yen’s algorithm: k 번 Dijkstra 변형. O(k V (V + E) log V).

최단 경로 DAG

Dijkstra/Bellman-Ford 에서 dist[v] == dist[u] + w 인 간선만 남기면 최단 경로 DAG.

실시간 갱신

간선 가중치가 동적으로 바뀌면 매번 재계산 필요. 휴리스틱: A* (heuristic function h), Bidirectional Dijkstra.

함정

1. 음수 간선 체크 안 함

Dijkstra 는 음수 간선 있으면 틀림. dist[v] 확정 후 다시 바뀔 수 있음.

2. 자기 루프 / 중복 간선

dist[u][u] = 0 초기화 누락 시 Floyd-Warshall 오류. 중복 간선은 min 으로 처리.

3. INF 오버플로우

INF + w 가 오버플로우하면 relax 조건 깨짐. INF = 1e18 (C++ long long), float('inf') (Python).

4. Dijkstra priority_queue 중복 pop

if (d > dist[u]) continue; 없으면 같은 노드를 여러 번 relax. 시간 초과.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 1753	최단경로 (Dijkstra)	-	kokoa-lab
BOJ 11657	타임머신 (Bellman-Ford)	-	kokoa-lab
BOJ 11404	플로이드 (Floyd-Warshall)	-	kokoa-lab
BOJ 1916	최소비용 구하기	-	kokoa-lab
BOJ 13549	숨바꼭질 3 (0-1 BFS)	-	kokoa-lab

참고

이 글의 용어 (6개)

0-1 BFSalgorithm: 정의 0-1 BFS 는 간선 가중치가 0 또는 1만 존재하는 그래프에서 최단 경로를 O(V + E) 에 구하는 알고리즘. deque 를 사용해 가중치 0 간선은 앞에, 가중치 1…
너비 우선 탐색 (BFS)algorithm: 정의 너비 우선 탐색 (Breadth-First Search, BFS) 는 그래프 G=(V, E) 에서 시작 정점 s 로부터 가까운 정점부터 순서대로 방문하는 알고리즘. 큐 (F…
다익스트라 알고리즘 (Dijkstra's Algorithm)algorithm: 정의 다익스트라 알고리즘 (Dijkstra's Algorithm) 은 음이 아닌 가중치 그래프에서 단일 시작점 s 로부터 모든 정점까지의 최단 거리를 찾는 그리디 알고리즘. Ed…
벨만-포드 알고리즘 (Bellman-Ford Algorithm)algorithm: 정의 벨만-포드 알고리즘 (Bellman-Ford Algorithm) 은 음수 가중치 간선을 허용하면서 단일 시작점 s 로부터 모든 정점까지의 최단 거리를 찾는 DP 기반 알고리…
최소 비용 최대 유량 (Min-Cost Max-Flow, MCMF)algorithm: 정의 최소 비용 최대 유량 (Min-Cost Max-Flow, MCMF) 은 각 간선에 용량(capacity)과 단위 비용(cost)이 주어질 때, 최대 유량을 달성하는 여러 방…
플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)algorithm: 정의 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) 은 모든 정점 쌍 (i, j) 사이의 최단 거리를 구하는 DP 알고리즘. Robert W. Floyd…

최단 경로 (Shortest Path)

정의

문제 상황과 동기

시각화

알고리즘 선택 가이드

핵심 아이디어

Relax 연산

BFS (가중치 1)

Dijkstra (음수 간선 없음)

Bellman-Ford (음수 간선 가능)

Floyd-Warshall (모든 쌍)

구현

BFS (가중치 1)

Dijkstra (음수 간선 없음)

Bellman-Ford (음수 간선 가능)

Floyd-Warshall (모든 쌍)

복잡도

변형 / 활용

경로 복원

k번째 최단 경로

최단 경로 DAG

실시간 갱신

함정

1. 음수 간선 체크 안 함

2. 자기 루프 / 중복 간선

3. INF 오버플로우

4. Dijkstra priority_queue 중복 pop

BOJ 연습 문제

참고

이 개념을 다룬 위키 페이지 (2)

💬 댓글