가장 가까운 곳부터 확정하자냥! 다익스트라

• 가중치가 있으면 BFS 가 안 되는 이유를 안다.
• 다익스트라를 우선순위 큐로 짠다.
• 음수 간선에는 못 쓴다는 걸 안다.
• 경유지와 다중 출발로 응용한다.
• 역방향 그래프로 돌아오는 길을 구한다.

비유로 이해하기 — 지하철 vs 걷기

A 에서 B 로 한 정거장 바로 가는 길이 있고, C 를 거쳐 두 정거장 돌아가는 길도 있다냥. 정거장 수만 세는 BFS 는 "한 정거장" 이 짧다고 한다냥.

그런데 그 한 정거장이 아주 먼 거리고, 돌아가는 두 정거장이 가까우면? BFS 는 틀린다냥. 거리(가중치) 를 봐야 하는데 정거장 수 만 봤기 때문이라냥.

BFS 는 간선을 전부 1로 본다냥.

그래서 가중치가 다른 그래프에서 BFS 로 거리를 세면 틀린다냥. 오늘 1번 문제를 BFS 로 풀면 바로 걸린다냥. 가중치가 있으면 다익스트라라냥.

비유로 이해하기 — 물결이 번지는 속도가 다르다냥

BFS 는 물결이 일정한 속도로 동그랗게 퍼졌다냥. 다익스트라는 길마다 속도가 다른 물결이라냥. 그래서 "지금 가장 먼저 도착할 곳"을 매번 골라야 한다냥. 그걸 우선순위 큐가 해준다냥.

if d > dist[u]: continue 를 꼭 넣자냥.

큐에는 같은 노드가 여러 번 들어갈 수 있다냥. 예전의 더 긴 거리가 남아 있을 수 있다냥. 꺼냈을 때 이미 더 짧은 거리로 확정됐으면 버려야 한다냥.

이걸 빼도 답은 맞지만, 쓸데없는 일을 반복해 느려진다냥. 습관으로 넣자냥.

거리는 아주 커질 수 있다냥.

간선이 4000개, 각 비용이 100만이면 거리가 40억까지 간다냥. 파이썬은 괜찮지만 다른 언어면 long/int64 를 쓰자냥. int 로 두면 넘친다냥.

왜 음수면 안 되냥?

다익스트라는 "가장 가까운 걸 확정하면 다시는 안 바뀐다" 를 믿는다냥. 이건 12장 그리디의 정신이라냥 — 눈앞에서 제일 가까운 걸 덥석 확정하는 거라냥.

그런데 음수 간선이 있으면, 나중에 음수 길을 타고 와서 이미 확정한 거리가 더 짧아질 수 있다냥. 확정을 못 믿게 되는 거라냥. 그러면 다익스트라가 틀린다냥.

음수 간선이 있는 최단 경로는 벨만-포드라는 다른 방법을 써야 한다냥. 이 수업 범위를 넘으니, 오늘은 "음수가 있으면 다익스트라는 안 된다" 만 기억하자냥. 오늘 문제는 전부 양수라 걱정 없다냥.