네 점 S, A, B, T의 방향 연결은 아래 표가 전부예요. h는 임의의 실수이며 가중치는 길이나 시간이 아닌 자체 점수예요. S에서 출발해 T에서 끝나며 같은 점과 연결을 다시 지나도 돼요. 다만 연결을 통과하는 전체 횟수는 정수 M≥1 이하로 제한해요.
| 연결 | S→A | A→B | B→A | S→T | B→T |
|---|---|---|---|---|---|
| 가중치 | 0 | 1 | −2 | 5 | h |
이 제한 아래에서도 음수 순환 때문에 최솟값이 없을까요? 모든 M과 h에서 정확한 최솟값과 최적 선택을 구해 볼까요? S→T만 지나는 점수 5보다 엄격히 작은 값을 얻기 위해 필요한 최소 통과 횟수도 구해 볼까요?
T로 가는 기록은 두 종류뿐이에요. S→T로 바로 가거나, S→A→B에서 B→A→B를 k번 반복한 뒤 B→T로 끝나요. 두 번째 기록의 통과 횟수는 3+2k, 점수는 1+h−k입니다. k는 0 이상 정수예요.
M=1,2이면 두 번째 기록은 허용되지 않아 최솟값은 5입니다. M≥3이면 반복할수록 점수가 엄격히 줄어 허용된 가장 큰 k를 택해요. 바닥 기호는 해당 수 이하의 가장 큰 정수예요.
h<4+K이면 순환을 K번 넣은 기록만 최적이에요. h=4+K이면 바로 가기와 K번 반복하기가 함께 최적이고, h>4+K이면 바로 가기만 최적이에요. 덜 반복한 우회 기록은 점수가 더 크므로 새로운 최적 후보가 아니에요.
처음으로 점수 5보다 작아지려면 정수 k가 h−4보다 커야 해요. 따라서
예를 들어 h=6이면 M=7,8에서 K=2라 바로 가기와 우회 점수가 모두 5입니다. M=9가 되어야 K=3으로 우회 점수가 4가 돼요. 한 번 더 통과할 수 있는 M=8은 반복 두 연결을 완성하지 못하므로 값을 줄이지 못해요.
반면 h=11/2이면 M=7에서 이미 점수가 9/2입니다. h의 정수·비정수 경계와 ‘엄격히 작다’는 조건이 최소 M을 바꿔요. 각 유한 M에서는 가능한 기록이 유한하고 바로 가기가 있으므로 최솟값을 실제로 얻어요. M 제한을 없애면 k를 끝없이 늘려 점수를 아래로 무한히 낮출 수 있어요. B→T를 아예 지우면 순환에서 T로 갈 수 없으므로 M 제한 없이도 최소는 5입니다.
MIT 강의에서 목표로 빠져나갈 수 있는 음수 순환은 제한 없는 최솟값을 없앤다는 조건을 읽었어요. 그 알려진 판정을 그대로 새 핵심으로 세지 않고, 횟수 예산과 출구 비용을 함께 둔 자체 문제에서 가능한 모든 기록과 선택 경계를 계산했어요.
교사는 음수 순환을 찾은 답에 반복 횟수의 허용 범위를 먼저 쓰게 해요. 음수 순환이 있다는 말은 유한 예산의 최소가 없다는 뜻이 아니에요. 예산을 한 번 늘린 것과 순환 한 번을 더 완성한 것도 다르므로, 두 연결짜리 반복의 홀짝 경계를 확인해요.
착안 원문: MIT 6.006, Lecture 17: Bellman-Ford (Fall 2011). 방향 연결과 횟수 예산·출구 점수의 분류는 자체 교육용 모형이며 실제 도로의 길이나 통행 비용을 보고한 것이 아니에요.