네 점 S, A, B, T의 방향 연결과 가중치는 아래 표가 전부예요. 가중치는 이동 거리나 시간이 아닌, 더하여 평가하는 자체 점수예요. 순환은 없어요.
| 연결 | S→A | S→B | B→A | A→T |
|---|---|---|---|---|
| 가중치 | 2 | 5 | −4 | 2 |
S의 추정값은 0, 나머지는 ∞로 시작해요. 미확정점 중 유한한 추정값이 가장 작은 점을 확정하고, 그 점에서 미확정점으로 나가는 연결로 추정값을 낮춘다. 확정점은 다시 고치지 않으며 T가 확정되면 종료해요. 이 절차가 구한 S→T의 값과 실제 최솟값을 비교해 볼까요? 순환이 없다는 조건이 이 절차를 보장하는가?
S를 처리하면 A는 2, B는 5입니다. A를 먼저 확정해 T를 4로 만들어요. 다음에는 T의 4가 B의 5보다 작아 T를 확정하고 끝나요. 절차의 답은 4입니다.
하지만 가능한 S→T 경로는 S→A→T와 S→B→A→T이고 값은 4와 3입니다.
B에 도착하는 값 5가 크더라도 뒤의 −4가 전체를 줄여요. A와 T를 너무 일찍 확정한 거예요. 순환이 없다는 것만으로 이 확정 순서가 옳아지지 않아요.
모든 가중치가 0 이상일 때는 최단경로의 앞부분 값이 마지막 값보다 커지지 않아요. 앞서 확정한 점들의 추정값이 실제 최단값과 같다는 귀납 가정을 둬요. 시작점 S의 값 0에서 출발해요. 확정할 점 v로 가는 최단경로에서 첫 미확정점을 y라 해 볼까요? 그 앞 점을 처리했으므로 y의 추정값은 실제 최단값 이하이며, 경로의 뒤쪽 가중치 합이 비음수이므로 그 값은 v의 실제 최단값 이하예요. 현재 추정값이 최소인 v는 y보다 작거나 같고, 모든 유한 추정값은 실제 경로의 값이므로 실제 최솟값 이상이에요. 양쪽 부등식이 맞물려 v의 추정값이 실제 최단값과 같아져요. 0인 가중치에서 동점이 생겨도 이 부등식 논리는 유지돼요.
MIT 강의의 비음수 가중치 조건과 확정 시점 증명에 착안했어요. 원문 예제의 점·연결·가중치를 바꾼 것이 아니라, 순환이 없는 반례를 별도로 만들고 실패에 필요한 조건을 검사했어요. 음수는 자체 점수에서의 공제이며 음의 길이를 뜻하지 않아요.
교사는 계산을 틀렸다고만 말하는 답에 어느 확정이 되돌아가야 하는지 물어요. 그런 뒤 비음수 조건을 쓴 부등식 한 곳을 표시하게 해요. 순환 유무와 현재 최소를 확정할 수 있는지는 별개의 조건이에요.
착안 원문: MIT 6.006, Lecture 13: Dijkstra’s Algorithm (Spring 2020). 네 점의 방향 연결과 부호 있는 점수는 자체 반례이며 실제 도로의 거리나 강의의 예제 가중치를 옮긴 것이 아니에요.