다음 네트워크에서 출발지 S로부터 도착지 F까지 최단경로의 거리는? (… | [물류관리사] 24년 1회차 기출문제 상세 페이지

S에서 F까지의 최단경로는 S→a→c→b→e→F이고 거리는 10 km다.
네트워크의 구간 거리는 S-a 2, S-c 7, S-b 7, a-c 2, a-d 7, c-b 2, c-d 4, c-e 6, b-e 2, d-e 6, d-F 5, e-F 2(단위 km)로 주어져 있다.
S에서 각 노드까지의 최소거리를 차례로 확정하면 a = 2, c = 2 + 2 = 4, b = 4 + 2 = 6, e = 6 + 2 = 8, d = 4 + 4 = 8이 된다.
F로 들어가는 경로는 e를 거치는 8 + 2 = 10과 d를 거치는 8 + 5 = 13뿐이므로 최단거리는 10 km다.
S에서 c나 b로 직접 가는 구간은 각각 7 km여서, a를 경유해 2 + 2로 c에 도달하는 경로보다 불리하다.