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

각 구간 거리를 더해 비교하면 출발지 A에서 목적지 H까지의 최단경로 산출거리는 7km이다.
그림의 간선 값은 A→B 1, A→D 2, A→E 3, B→C 3, B→D 2, D→C 2, D→F 2, D→G 5, C→G 4, E→F 4, F→G 2, F→H 4, G→H 1이다.
H로 들어오는 길은 G→H(1)와 F→H(4) 둘뿐이므로 F와 G까지의 최단거리를 먼저 구한다.
A→D = 2, D→F = 2 이므로 A~F 최단 = 4
G는 F를 거치는 4 + 2 = 6이 최소이다(A→D→G는 2+5=7, A→D→C→G는 2+2+4=8, A→B→C→G는 1+3+4=8).
따라서 A→D→F→G→H = 2 + 2 + 2 + 1 = 7이며, F에서 곧바로 H로 가는 A→D→F→H(2+2+4=8)나 A→D→G→H(2+5+1=8)보다 짧다.