다익스트라로 최단 거리 구하기
간선마다 이동 시간이 다르면 BFS가 찾는 ‘간선 수가 적은 길’이 가장 빠른 길은 아닙니다. 다익스트라는 현재 알려진 거리가 가장 작은 정점부터 처리합니다. 모든 가중치가 0 이상이어야 합니다.
거리를 줄일 때만 다시 넣기
정점 이름은 문자열이고, 모든 정점을 딕셔너리의 키로 등록합니다. 이 예제의 간선은 방향이 있습니다. A에서 B로 3, B에서 C로 2, A에서 C로 8이 걸립니다.
import heapq
def shortest_distances(graph, start):
if any(w < 0 for edges in graph.values() for w in edges.values()):
raise ValueError("Nonnegative weights required")
distance = {node: float("inf") for node in graph}
distance[start] = 0
pending = [(0, start)]
while pending:
cost, node = heapq.heappop(pending)
if cost != distance[node]:
continue
for neighbor, weight in graph[node].items():
candidate = cost + weight
if candidate < distance[neighbor]:
distance[neighbor] = candidate
heapq.heappush(pending, (candidate, neighbor))
return distance
graph = {"A": {"B": 3, "C": 8}, "B": {"C": 2}, "C": {}}
print(shortest_distances(graph, "A")["C"])
출력은 5입니다. A에서 C로 바로 가는 8보다 B를 거치는 5가 짧습니다. 같은 정점이 힙에 여러 번 들어갈 수 있습니다. 이전 거리로 넣었던 항목은 꺼냈을 때 현재 거리와 비교해 건너뜁니다.
왜 가장 가까운 곳부터 확정할까요?
모든 간선 비용이 0 이상이면, 지금보다 먼 정점을 거쳐 돌아오는 길로 현재 최소 거리를 더 줄일 수 없습니다. 이 전제가 음수 간선에서는 깨집니다. 음수 간선이 필요한 문제에는 벨만-포드처럼 다른 방법을 검토해야 합니다.
단순 그래프와 이진 힙을 쓰면 시간은 O((V+E) log V)입니다. 도달할 수 없는 정점의 거리는 무한대로 남습니다. 실제 경로도 필요하면 거리를 갱신할 때 이전 정점을 함께 저장해 역순으로 따라갑니다.
확인 문제
A에서 B가 3, A에서 C가 5, C에서 B가 -4라면 A-B의 최단 거리는 얼마인가요? 다익스트라의 기본 확정 규칙을 그대로 믿어도 될까요?
해설 보기
A-C-B로 가면 1입니다. B를 거리 3으로 먼저 확정해 끝내면 틀립니다. 음수 간선 때문에 전제가 깨진 것입니다. 위 구현은 이런 입력을 허용하지 않습니다.