다음과 같은 네트워크에서 노드 S로부터 다른 모든 노드에 원유를 공급하… | [물류관리사] 11년 1회차 기출문제 상세 페이지

모든 노드를 잇는 가장 짧은 송유관 네트워크는 최소신장트리로 구하며, 그 총길이는 19km이다.
주어진 구간 거리는 S–A 2, S–B 5, S–C 4, A–B 3, A–D 3, A–E 4, B–C 1, B–E 3, B–F 6, C–F 5, D–E 2, D–G 5, E–F 7, E–G 3, F–G 6이다. 짧은 구간부터 순환이 생기지 않게 골라 나가면 B–C 1, S–A 2, D–E 2, A–B 3, A–D 3, E–G 3이 차례로 채택된다.
여기까지 노드 F만 연결되지 않는데, F로 이어지는 구간 중 가장 짧은 것이 C–F 5이므로 이를 더한다. 노드 8개를 잇는 데 필요한 구간은 7개이고 그 합은 1+2+2+3+3+3+5 = 19km이다. S–C 4, A–E 4, B–E 3 등은 이미 연결된 노드끼리를 다시 잇는 순환 구간이라 제외되며, 최단경로 문제가 아니라 모든 노드를 최소 길이로 잇는 문제임에 유의해야 한다.