7개의 마디{O, A, B, C, D, E, T}와 한 쌍의 마디를 양… | [서울시 연구사 경영과학] 14년 1회차 기출문제 상세 페이지

1[서울시 연구사 경영과학] 14년 1회차
7개의 마디{O, A, B, C, D, E, T}와 한 쌍의 마디를 양방향으로 연결하는 12개의 가지{OA, OB, OC, AB, AD, BC, BD, BE, CE, DE, DT, ET}로 이루어진 네트워크에 대해 다음과 같이 마디 간의 거리가 주어진 경우 출발점 O에서 목적지 T까지의 최단 경로에 포함되지 않는 가지는?
가지거리가지거리가지거리
O-A3A-D8C-E5
O-B6B-C1D-E1
O-C5B-D5D-T5
A-B1B-E3E-T8
1
O-A
2
A-B
3
B-D
4
B-E
5
D-T
해설

최단 경로는 O-A-B-E-D-T(길이 13)이며, 여기에 포함되지 않는 가지는 B-D이다.

출발점에서 가까운 마디부터 최단거리를 확정한다.
A: 3 (O-A)
B: min(6, 3+1) = 4 (O-A-B)
C: min(5, 4+1) = 5
E: min(4+3, 5+5) = 7 (B-E)
D: min(3+8, 4+5, 7+1) = 8 (E-D)
T: min(8+5, 7+8) = 13 (D-T)

B에서 D로 바로 가면 9이지만 B-E-D로 돌아가면 8이므로 B-D 가지는 쓰이지 않는다.

  • O-A: 출발점에서 A로 가는 첫 가지로 최단 경로에 포함된다.
  • A-B: O에서 B까지 거리 4로 가는 데 쓰인다.
  • B-E: B에서 E로 이어 E까지 거리 7을 만든다.
  • D-T: D에서 목적지 T로 가는 마지막 가지다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[서울시 연구사 경영과학] 14년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요서울시 연구사 경영과학 기출문제 암기장 전체 보기