배송센터 L로부터 모든 수요지점 1 ～ 6까지의 최단 경로 네트워크를 … | [물류관리사] 17년 1회차 기출문제 상세 페이지

배송센터 L에서 각 수요지점까지의 최단경로만 남긴 네트워크의 전체 거리는 12 km이다.
그림의 구간 거리는 L-1 3, L-2 7, 1-2 3, 1-3 2, 1-4 1, 2-3 3, 2-5 2, 3-4 4, 3-5 3, 4-5 4, 4-6 2, 5-6 1 km이다.
L 기준 최단거리를 구하면 1까지 3, 4까지 4(L-1-4), 3까지 5(L-1-3), 2까지 6(L-1-2로 L-2 직결 7보다 짧다), 6까지 6(L-1-4-6), 5까지 7(L-1-4-6-5로 L-1-2-5의 8보다 짧다)이다.
이때 실제로 사용되는 구간은 L-1(3), 1-4(1), 1-3(2), 1-2(3), 4-6(2), 6-5(1)이므로 전체 거리는 $3+1+2+3+2+1=12\ \mathrm{km}$이다. L-2 7 km 구간은 우회로가 더 짧아 최단경로망에서 빠진다는 점이 함정이다.