다음 그림과 같이 각 구간별 운송시간이 주어졌을 때, 출발지에서 도착지… | [물류관리사] 08년 1회차 기출문제 상세 페이지

출발지에서 도착지까지의 최단 시간은 11시간이며, 경로는 출발 → 가 → 라 → 다 → 나 → 바 → 도착이다.
그림의 구간 시간은 출발–가 4, 출발–나 8, 가–라 1, 가–다 3, 가–나 4, 라–다 1, 라–마 3, 라–도착 7, 다–나 1, 다–바 4, 나–바 2, 마–바 3, 바–도착 2시간이다.
최단 경로를 따라 합산하면 $4 + 1 + 1 + 1 + 2 + 2 = 11$시간이 된다. 도착지 직전 구간이 라–도착 7시간보다 바–도착 2시간이 훨씬 짧으므로, 바를 경유하도록 경로를 잡는 것이 관건이다.
다른 경로는 모두 이보다 길다. 출발–가–라–도착은 4+1+7=12시간, 출발–가–다–나–바–도착은 4+3+1+2+2=12시간, 출발–나–바–도착은 8+2+2=12시간이다. 즉 가–라–다를 1시간씩 타고 내려와 나를 거쳐 바로 진입하는 우회로가 직행처럼 보이는 경로보다 빠르다는 점이 이 문제의 함정이다.