최단경로·MST

다익스트라

길마다 걸리는 시간이 다르면

시간이 0 이상이어야 확정을 믿을 수 있다

• 확정한 곳은 끝 — 가장 가까운 곳이다. 길이 모두 0분 이상이면 다른 곳을 거쳐 와도 더 짧아지지 않는다
• 음수 시간이 있으면 — S→A 1분, S→B 2분, B에서 A로만 가는 한 방향 길이 −3분이면 A는 1분에 확정했는데 실제로는 −1분이다
• ① 에서 먼 곳을 못 누른 이유 — 더 가까운 곳이 남아 있으면 그곳을 거쳐 더 짧게 오는 길이 있을 수 있다
• 걸리는 일 — 길마다 큐에 한 번 넣고 꺼내니 많아야 길 수 × log. 길이 100,000개면 약 1,660,964번, 1초 안에 끝난다

코드는 큐에서 가장 작은 거리를 꺼내는 반복이다

코드 위에 import heapq 한 줄이 있다고 치세요. 다음을 눌러 한 줄씩 넘기며 거리표와 큐가 바뀌는 걸 보세요.

36스텝입니다. while·for 머리줄(5·9번)과 낡은 항목을 거르는 7번 줄은 건너뜁니다. 낡은 항목이 나올 때만 8번 줄이 켜집니다.

• heapq.heappop(heap) — 큐에서 거리가 가장 작은 (거리, 곳)을 꺼낸다
• if d > dist[u]: continue — 지금 기록보다 큰 낡은 항목은 건너뛴다
• if d + w < dist[v] — 더 짧을 때만 고쳐 적고 큐에 넣는다
• (d + w, v) — 큐에는 거리를 앞에 둔다. 그래야 가장 가까운 곳부터 나온다

다익스트라에서 틀리는 자리

• if d > dist[u]: continue 를 빼면 — 답은 같지만 낡은 항목의 이웃까지 다시 본다. 이 지도에서 길 확인이 14번에서 17번으로 늘어난다
• 거리를 0 으로 시작하면 — 어떤 길도 “더 짧다”로 보이지 않아 아무것도 고쳐지지 않는다. 결과가 모두 0분이다. 처음 값은 float('inf')
• 큐에 (v, d + w) 순서로 넣으면 — 곳 이름순으로 꺼내져 “가까운 곳 먼저”가 깨진다. 답은 같지만 이 지도에서 8번 꺼내고 7번 고쳐 적는다(제대로면 7번·6번)
• 음수 길이는 — 이 코드는 낡은 값을 고쳐 다시 큐에 넣어서 음수 길이 한두 개는 맞는 답을 낸다. 하지만 돌수록 시간이 줄어드는 순환이 있으면 끝나지 않는다. 실제로 2,000번 꺼내도 거리가 계속 줄었다

문제에서 이 말이 보이면

다음 장에서는 같은 계산을 두 번 하지 않는 메모이제이션을 봅니다.