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

그림의 구간거리를 누적하면 S→A→B→E→G 경로가 최단이며 산출거리는 14km이다.
주어진 구간거리는 S-A 4, S-B 6, S-C 5, A-B 1, A-D 5, A-E 6, B-C 4, B-E 4, B-H 6, C-E 7, C-H 5, D-E 3, D-G 6, E-G 5, H-G 8(km)이다.
각 노드까지의 최소 누적거리를 구하면 A=4, B=4+1=5, C=5, D=4+5=9, E=5+4=9, H=5+5=10이 된다.
목적지 G에 이르는 경로를 마지막 구간별로 비교하면 다음과 같다.
E 경유: 9+5=14km
D 경유: 9+6=15km
H 경유: 10+8=18km
따라서 S에서 A(4)로 간 뒤 B(1), E(4)를 거쳐 G(5)에 이르는 14km가 최단이며, S-A-D-G의 15km나 S-C-H-G의 18km는 이보다 길다.