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

S에서 F까지의 최단경로 거리는 25km이며, 경로는 S→b→c→d→F다.
그림의 간선 거리는 S-a 8, S-b 10, S-c 15, a-b 7, a-c 8, a-d 11, a-F 19, b-c 3, b-e 8, c-d 2, c-e 4, c-F 14, d-F 10, e-F 9(km)이다.
각 노드까지의 최단거리를 차례로 구하면 a=8, b=10(S-b 직결), c=13(S-b 10 + b-c 3), d=15(c 13 + c-d 2), e=17(c 13 + c-e 4)이다.
F까지는 a 경유 8+19=27, c 경유 13+14=27, e 경유 17+9=26, d 경유 15+10=25이므로 최솟값은 25km다.