<보기 1>의 가중치 방향 그래프 G에 대해 모든 정점 쌍의… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지

1[7급 서울시 알고리즘] 26년 1회차
<보기 1>의 가중치 방향 그래프 G에 대해 모든 정점 쌍의 최단 경로를 구하는 플로이드-워셜(Floyd-Warshall) 알고리즘을 수행하는 과정에서 <보기 2>의 행렬 D2D_2를 얻었다. 다음 단계에서 얻을 행렬 D3D_3의 2행으로 가장 옳은 것은? (단, Dk[i, j]D_k[i,\ j]는 정점 ii에서 정점 jj로 가는 경로 중 중간 정점이 모두 1번부터 kk번 사이의 정점인 최단 경로의 길이이고, 그러한 경로가 없으면 ∞이다.)
<보기 1>
<보기 2>
12345
10411012
2∞0-3∞8
3590217
4∞∞∞03
5∞∞-1∞0
D2D_2

문제 이미지
1
(∞, 0, -3, ∞, 8)
2
(∞, 0, -3, ∞, 2)
3
(2, 0, -3, -1, 8)
4
(2, 0, -3, -1, 2)
해설

D3D_3의 2행은 (2, 0, -3, -1, 8)이다.

정점 3을 중간 정점으로 새로 허용하므로 D3[2,j]=min⁡(D2[2,j], D2[2,3]+D2[3,j])D_3[2,j]=\min(D_2[2,j],\ D_2[2,3]+D_2[3,j])이고, D2[2,3]=−3D_2[2,3]=-3, D2D_2의 3행은 (5, 9, 0, 2, 17)이다.

j=1j=1: min⁡(∞, −3+5)=2\min(\infty,\ -3+5)=2
j=2j=2: min⁡(0, −3+9)=0\min(0,\ -3+9)=0
j=4j=4: min⁡(∞, −3+2)=−1\min(\infty,\ -3+2)=-1
j=5j=5: min⁡(8, −3+17)=8\min(8,\ -3+17)=8

  • 1열과 4열을 ∞로 둔 행: 2→3→1, 2→3→4 경로가 생겨 각각 2, -1로 갱신되어야 한다.
  • 5열을 2로 둔 행: 2→3→5는 14로 기존 8보다 크므로 5열은 8 그대로이다(2는 정점 4를 거치는 다음 단계 값).

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

이어서 풀어보기

[7급 서울시 알고리즘] 26년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 서울시 알고리즘 기출문제 암기장 전체 보기