다음 그래프에 대한 모든 쌍의 최단 경로를 구하기 위해 최단 거리 행렬… | [7급 국가직 자료구조론] 17년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 17년 1회차
다음 그래프에 대한 모든 쌍의 최단 경로를 구하기 위해 최단 거리 행렬 D-1, D0, D1, D2를 차례대로 구한다고 했을 때, D1의 계산 결과는?
문제 이미지
1
[0][1][2]
[0]03∞
[1]602
[2]140
2
[0][1][2]
[0]035
[1]602
[2]140
3
[0][1][2]
[0]035
[1]302
[2]140
4
[0][1][2]
[0]03∞
[1]602
[2]150
해설

플로이드 알고리즘으로 정점 V(0), V(1)까지 경유를 허용한 D^1은 0행이 0, 3, 5 / 1행이 6, 0, 2 / 2행이 1, 4, 0인 행렬이다.

그래프의 간선은 V(0)→V(1) 3, V(1)→V(0) 6, V(1)→V(2) 2, V(2)→V(0) 1, V(2)→V(1) 5이며, 이것이 초기 행렬 D^-1이다.

D^0(V(0) 경유): D[2][1]=min⁡(5, 1+3)=4D[2][1]=\min(5,\ 1+3)=4
D^1(V(1) 경유): D[0][2]=min⁡(∞, 3+2)=5D[0][2]=\min(\infty,\ 3+2)=5, D[2][0]=min⁡(1, 4+6)=1D[2][0]=\min(1,\ 4+6)=1

  • [0][2]가 ∞이고 [2][1]이 4인 행렬은 V(0)만 경유한 D^0이다.
  • [0][2]가 ∞이고 [2][1]이 5인 행렬은 경유 없는 초기 행렬 D^-1이다.
  • [1][0]이 3인 행렬은 V(2)까지 경유(6 대신 2+1)한 D^2로, D^1 단계에서는 아직 반영되지 않는다.

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

이어서 풀어보기

[7급 국가직 자료구조론] 17년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기