다음 그래프에 대한 모든 쌍의 최단 경로를 구하기 위해 최단 거리 행렬… | [7급 국가직 자료구조론] 17년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 17년 1회차
다음 그래프에 대한 모든 쌍의 최단 경로를 구하기 위해 최단 거리 행렬 D-1, D0, D1, D2를 차례대로 구한다고 했을 때, D1의 계산 결과는?
1
| [0] | [1] | [2] | |
|---|---|---|---|
| [0] | 0 | 3 | ∞ |
| [1] | 6 | 0 | 2 |
| [2] | 1 | 4 | 0 |
2
| [0] | [1] | [2] | |
|---|---|---|---|
| [0] | 0 | 3 | 5 |
| [1] | 6 | 0 | 2 |
| [2] | 1 | 4 | 0 |
3
| [0] | [1] | [2] | |
|---|---|---|---|
| [0] | 0 | 3 | 5 |
| [1] | 3 | 0 | 2 |
| [2] | 1 | 4 | 0 |
4
| [0] | [1] | [2] | |
|---|---|---|---|
| [0] | 0 | 3 | ∞ |
| [1] | 6 | 0 | 2 |
| [2] | 1 | 5 | 0 |
해설
플로이드 알고리즘으로 정점 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^1(V(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 단계에서는 아직 반영되지 않는다.
오류나 개정된 내용이 보이면 알려주세요
