최단경로와 단계별 갱신

간선을 적게 타는 길과 비용이 적은 길은 다를 수 있습니다. 그래프 표현을 바탕으로 간선 무게·출발점·음수 여부에 맞는 방법을 선택합니다.

무게 없는 그래프와 가중치 그래프

모든 간선 비용이 같으면 BFS는 출발점에서 간선 수가 최소인 거리를 구합니다. 가중치가 다르면 간선 수만 최소화해도 비용이 최소라는 보장은 없습니다. 무방향 간선 AB=2,AC=5,BC=1,BD=6,CD=2를 사용하면 A→B→C→D의 비용 5가 A→C→D의 7보다 작습니다.

Dijkstra는 음수가 없는 무게

아직 확정하지 않은 정점 중 현재 거리가 최소인 정점을 선택합니다. 그 정점을 통해 다른 정점으로 가는 비용이 더 작으면 갱신하는 것을 완화(relaxation)라 합니다. 무게가 음수가 아니므로 나중에 더 먼 정점을 거쳐 확정한 거리를 낮출 수 없다는 성질을 사용합니다.

B를 통해 C를 2+1=3으로, D를 2+6=8로 갱신합니다. 이어 C를 통해 D를 3+2=5로 낮춥니다. 거리만 적으면 실제 경로가 사라지므로 갱신할 때 이전 정점도 기록합니다.

from heapq import heappush, heappop

def dijkstra(graph, start):
    if any(w < 0 for edges in graph.values() for _, w in edges):
        raise ValueError('음수 가중치는 허용하지 않습니다')
    distance = {v: float('inf') for v in graph}
    distance[start] = 0
    parent = {}
    heap = [(0, start)]
    while heap:
        cost, v = heappop(heap)
        if cost != distance[v]:
            continue  # 더 좋은 값으로 갱신된 예전 항목
        for u, weight in graph[v]:
            candidate = cost + weight
            if candidate < distance[u]:
                distance[u] = candidate
                parent[u] = v
                heappush(heap, (candidate, u))
    return distance, parent

graph = {'A': [('B',2),('C',5)],
         'B': [('A',2),('C',1),('D',6)],
         'C': [('A',5),('B',1),('D',2)],
         'D': [('B',6),('C',2)]}
print(dijkstra(graph, 'A')[0])  # {'A': 0, 'B': 2, 'C': 3, 'D': 5}

Python 3과 표준 라이브러리만 사용합니다. 모든 이웃은 graph의 키에 있어야 하고 시작점도 키에 있어야 합니다. 정점 이름은 이 예제처럼 문자열이라 힙에서 거리가 같은 항목을 비교할 수 있습니다. 임의 객체를 이름으로 쓴다면 별도의 순번을 넣어 비교 문제를 해결해야 합니다.

Floyd-Warshall은 모든 쌍

거리행렬 D는 대각선을 0으로, 직접 간선이 있는 자리를 무게로, 간선이 없는 자리를 ∞로 초기화합니다. 중간 정점 k를 하나씩 허용하며 $D_{ij}=\min(D_{ij},D_{ik}+D_{kj})$로 갱신합니다. k가 바깥 반복이며 n³번 계산합니다. 음수 간선도 다룰 수 있지만 도달 경로에 음수 사이클이 있으면 계속 더 작게 돌아서 최단거리가 유한하게 정해지지 않습니다. 계산 후 음수 대각선은 음수 사이클의 신호입니다.

스스로 풀어보기

문제 1. 위 예제에서 A→D 최단경로와 비용을 중간값으로 확인하세요.

풀이: A→B→C→D로 2+1+2=5입니다. 후보 A→B→D는 8, A→C→D는 7이라 더 큽니다. 표의 D=8에서 5로 낮아진 단계가 C 확정 단계입니다.

문제 2. A→B=1,A→C=2,C→B=-3인 방향 그래프에서 Dijkstra를 그대로 적용하면 왜 문제가 생기나요?

풀이: B를 거리 1로 먼저 확정하지만 C를 거치면 A→C→B=-1입니다. 이후 경로가 확정 거리보다 작아져 확정 논리가 무너집니다. 예제 함수는 음수 간선을 검사해 거절합니다. 음수 간선에 맞는 다른 알고리즘이나 Floyd의 조건을 선택해야 합니다.

오답에서는 우선 무게 조건과 간선 없음 표기를 확인합니다. 탐색 순서 자체는 다음 DFS·BFS에서 별도로 익힙니다.