<보기 1>의 가중치 방향 그래프 G에 대해 모든 정점 쌍의… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지
1[7급 서울시 알고리즘] 26년 1회차
<보기 1>의 가중치 방향 그래프 G에 대해 모든 정점 쌍의 최단 경로를 구하는 플로이드-워셜(Floyd-Warshall) 알고리즘을 수행하는 과정에서 <보기 2>의 행렬 를 얻었다. 다음 단계에서 얻을 행렬 의 2행으로 가장 옳은 것은? (단, 는 정점 에서 정점 로 가는 경로 중 중간 정점이 모두 1번부터 번 사이의 정점인 최단 경로의 길이이고, 그러한 경로가 없으면 ∞이다.)<보기 1><보기 2>
1 2 3 4 5 1 0 4 1 10 12 2 ∞ 0 -3 ∞ 8 3 5 9 0 2 17 4 ∞ ∞ ∞ 0 3 5 ∞ ∞ -1 ∞ 0
1
(∞, 0, -3, ∞, 8)
2
(∞, 0, -3, ∞, 2)
3
(2, 0, -3, -1, 8)
4
(2, 0, -3, -1, 2)
해설
의 2행은 (2, 0, -3, -1, 8)이다.
정점 3을 중간 정점으로 새로 허용하므로 이고, , 의 3행은 (5, 9, 0, 2, 17)이다.
:
:
:
:
- 1열과 4열을 ∞로 둔 행: 2→3→1, 2→3→4 경로가 생겨 각각 2, -1로 갱신되어야 한다.
- 5열을 2로 둔 행: 2→3→5는 14로 기존 8보다 크므로 5열은 8 그대로이다(2는 정점 4를 거치는 다음 단계 값).
오류나 개정된 내용이 보이면 알려주세요
