[알고리즘] 최단 경로 알고리즘 정리

코딩테스트

[알고리즘] 최단 경로 알고리즘 정리

공영재 2025. 5. 9. 11:31

요약

- BFS : 모든 가중치가 같거나 가중치가 없는 탐색

- 다익스트라 : 음이 아닌 가중치 그래프

heapq 사용 + 방문 거리 갱신 조건 체크
큐에 여러 번 같은 노드가 들어갈 수 있음 → if distance[now] < dist 체크 필요
heapq를 사용하면 자동으로 비용이 작은 노드를 우선 방문
# 1. 거리 리스트 무한대로 초기화, 시작 노드 거리만 0
distance = [INF] * (n + 1)
distance[start] = 0
# 2. 우선순위 큐 (min-heap) 사용. (비용, 정점)
heap = [(0, start)]
# 3. 큐가 빌 때까지 반복
while heap:
current_dist, current_node = heappop(heap)
# 4. 이미 더 짧은 경로로 방문된 경우 무시
    if distance[current_node] < current_dist:
        continue
    # 5. 인접 노드 탐색
    for neighbor, weight in graph[current_node]:
        new_cost = current_dist + weight
        # 6. 더 짧은 경로라면 갱신 및 큐 삽입
        if new_cost < distance[neighbor]:
            distance[neighbor] = new_cost
            heappush(heap, (new_cost, neighbor))

- 벨만포드 : 음을 포함한 가중치 그래프

음수 사이클이 있으면 값이 계속 감소하므로 -1을 return
# 1. 거리 리스트 무한대로 초기화, 시작 노드 거리만 0
# 2. V-1번 모든 간선을 순회하며 거리 갱신
for i in range(n - 1):
    for u, v, w in edges:  # edges: (출발, 도착, 가중치)
        if distance[u] != INF and distance[u] + w < distance[v]:
            distance[v] = distance[u] + w
# 3. V번째 순회: 한 번 더 갱신되면 음수 사이클 존재
for u, v, w in edges:
if distance[u] != INF and distance[u] + w < distance[v]:
return -1 # 음수 사이클 감지

- 플로이드 워셜 : 그래프 내 모든 노드의 최단경로 전체

자기 자신으로 가는 거리는 0으로 초기화
중간 노드를 먼저 for문에
O(N^3)이므로 N이 작을 때만 사용 가능 (N ≤ 500 정도)
# 1. 거리 행렬 초기화 (자기 자신은 0, 연결된 곳은 cost, 나머지는 INF)
graph = [[INF] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
graph[i][i] = 0
# 간선 정보 입력
for a, b, cost in edges:
graph[a][b] = min(graph[a][b], cost)
# 2. 중간 노드 k를 기준으로 i→j 최단 거리 갱신
for k in range(1, n + 1):           # 중간 노드
    for i in range(1, n + 1): # 출발 노드
        for j in range(1, n + 1): # 도착 노드
            if graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]

BFS

개념

BFS는 시작 지점에서 가까운 노드부터 탐색해 나가는 알고리즘이다.
말 그대로 '넓게' 퍼져나가며 탐색하기 때문에, 모든 간선의 가중치가 같을 경우, 최단거리 문제에 적합하다.

Level by Level 탐색
같은 깊이에 있는 노드들을 먼저 전부 탐색한 다음, 그 다음 깊이의 노드로 넘어간다.
즉, 탐색하는 경로가 ‘단계별’로 진행된다.
동작 흐름
1. 시작 노드를 큐에 넣고, 방문 표시
2. 큐에서 노드를 꺼냄 → 인접한 노드들 중 방문하지 않은 노드들을 큐에 넣고 방문 표시
3. 큐가 빌 때까지 2번 반복
최단거리 보장 이유
큐에 넣는 순간은 ‘해당 노드를 처음 방문한 순간’이므로, 이때의 거리가 최단 거리임이 보장된다.
동일 가중치 그래프에서는 이 순서가 항상 최적이다.

예시

📌 1 → 2, 1 → 3, 2 → 4, 3 → 4 라는 간선이 있는 그래프에서,
1에서 4까지 가는 최단 경로는?

BFS는 이렇게 작동한다:

시작: 1
방문: 2, 3 (1의 인접 노드들)
그 다음: 4 (2와 3의 인접 노드)
→ 1 → 2 → 4 또는 1 → 3 → 4 (최단거리: 2)

구현

from collections import deque

def bfs(start):
    queue = deque([start])
    visited[start] = 1  # 시작 노드 방문 표시

    while queue:
        current = queue.popleft()
        for next_node in graph[current]:
            if not visited[next_node]:
                visited[next_node] = visited[current] + 1
                queue.append(next_node)

visited[node]에 해당 노드까지의 거리(=단계 수)를 저장 가능

다익스트라

개념

다익스트라는 간선의 가중치가 모두 양수일 때 사용할 수 있는 최단 경로 알고리즘이다.
시작점에서 다른 모든 노드까지의 최소 비용을 구하는 데 적합하다.

가장 가까운 노드부터 방문한다
→ "방문한 노드까지의 비용이 가장 작을 때만 방문한다."
즉, 방문 순서가 '가까운 노드' 우선으로 정해짐.
우선순위 큐 사용
매 순간 “현재까지의 비용이 가장 작은 노드”를 골라서 방문한다.
일반적인 큐 대신 Python의 heapq로 구현한다.

동작 방식

시작 노드의 거리를 0으로 초기화, 나머지는 무한대
시작 노드를 우선순위 큐에 넣음
큐에서 현재 거리가 가장 짧은 노드를 꺼냄
해당 노드에서 갈 수 있는 노드들의 거리를 계산해서 갱신함 (더 짧은 거리라면 업데이트)
큐가 빌 때까지 반복

예시

📌 1번 정점에서 다음과 같은 간선을 통해 최단 거리 찾기

1 → 2 (2)
1 → 3 (5)
2 → 3 (1)

초기 상태:
distance = [inf, 0, inf, inf]  # 시작점은 0

1 방문 → 2의 거리 = 2, 3의 거리 = 5
2 방문 → 3의 거리 = min(5, 2+1) = 3
3 방문 → 종료

최단 거리: 1 → 2 → 3 = 3

구현

import heapq

def dijkstra(start):
    distance = [INF] * (n + 1)
    distance[start] = 0
    pq = [(0, start)]

    while pq:
        dist, now = heapq.heappop(pq)
        if distance[now] < dist:
            continue
        for next_node, cost in graph[now]:
            new_cost = dist + cost
            if new_cost < distance[next_node]:
                distance[next_node] = new_cost
                heapq.heappush(pq, (new_cost, next_node))

벨만포드

개념

음수 간선이 존재할 수 있는 그래프에서 최단 거리를 구하는 알고리즘.
시작 정점 하나에서 모든 정점까지의 최단 거리를 계산할 수 있다.

다익스트라는 음수 간선을 처리할 수 없지만, 벨만포드는 가능하다.
단, 음수 사이클이 존재하면 최단 경로를 정의할 수 없기 때문에 탐색 실패로 간주한다.

동작 방식

시작 정점의 거리를 0, 나머지는 무한대로 초기화
전체 간선을 V-1번 순회하며 각 간선을 통해 거리 갱신
- 거리 갱신 공식:
  if distance[u] + w < distance[v]: distance[v] = distance[u] + w
V번째 순회에서 또 갱신이 발생하면 → 음수 사이클 존재

📌 핵심 아이디어:
"어떤 정점까지의 최단 경로는 최대 정점 수 - 1개의 간선을 거친다"는 점을 활용.

예시

정점 1에서 시작. 간선 정보는 다음과 같음:

1 → 2 (4)
1 → 3 (5)
2 → 3 (-2)

초기 상태: [inf, 0, inf, inf]
1번째 반복: 1→2: 0+4=4 → [0, 4, inf]
            1→3: 0+5=5 → [0, 4, 5]
            2→3: 4+(-2)=2 → [0, 4, 2]
2번째 반복: 갱신 없음 → 종료

최단 거리: 1 → 2 = 4, 1 → 3 = 2

구현

def bellman_ford(start):
    distance = [INF] * (n + 1)
    distance[start] = 0

    for i in range(n - 1):
        for u, v, w in edges:
            if distance[u] != INF and distance[v] > distance[u] + w:
                distance[v] = distance[u] + w

    # 음수 사이클 탐지
    for u, v, w in edges:
        if distance[u] != INF and distance[v] > distance[u] + w:
            return -1  # 음수 사이클 존재

    return distance

edges는 (u, v, weight) 형식의 간선 리스트

플로이드 워셜

개념

모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘.
인접 행렬을 기반으로 구현되며, 음수 간선은 허용하지만 음수 사이클은 없어야 한다.

📌 핵심 아이디어:
"i에서 j로 가는 최단 경로는, k라는 중간 정점을 거쳤을 때 더 짧아질 수 있다"
→ 이를 모든 i, j, k 조합에 대해 계산한다.

동작 방식

초기 거리 행렬을 세팅 (자기 자신은 0, 직접 연결된 건 그 값, 나머지는 INF)
정점 k를 중간 노드로 두고, i→j의 경로를
distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
위를 3중 for문으로 모두 갱신 → 모든 쌍 최단 거리 완성

예시

정점 1~3, 간선은 다음과 같음:

1 → 2 (4)
1 → 3 (11)
2 → 3 (2)

초기 행렬:
1→2 = 4, 1→3 = 11
2→3 = 2

중간 정점 k=2일 때:
1→3 = min(11, 1→2(4) + 2→3(2)) = 6
→ 최단 거리: 1→2→3

구현

# n: 정점 수
graph = [[INF] * (n+1) for _ in range(n+1)]

for i in range(1, n+1):
    graph[i][i] = 0  # 자기 자신은 0

for _ in range(m):
    a, b, cost = map(int, input().split())
    graph[a][b] = min(graph[a][b], cost)  # 간선 중복 대비

# 플로이드 워셜
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

예제