[7급 국가직 자료구조론 2010년 20번]

그래프에서 모든 정점 간의 최단 경로 비용을 구하기 위한 플로이드－워샬 알고리즘은 아래의 식으로 표현된다.

$A^k[i][j]=\min \left\{A^{k-1}[i][j],A^{k-1}[i][k]+A^{k-1}[k][j]\right\}$, $k>0$

$A^0[i][j]=\cos t[i][j]$

위의 식에서 $\cos t[i][j]$는 정점 $i$에서 정점 $j$로 가는 간선의 가중치를 나타내며, $A^k[i][j]$는 $k$보다 더 큰 인덱스를 갖는 정점을 통과하지 않으면서 $i$에서 $j$까지 갈 수 있는 최단 경로 비용을 나타낸다. 아래 그래프에 대해 행렬 $A^2$의 값으로 알맞은 것은?

1. ①$\left(\begin{array}{ccccc}0& 3& 8& 4& -4\\ \infty & 0& \infty & 1& 7\\ \infty & 4& 0& 5& 11\\ 2& -1& -5& 0& -2\\ \infty & \infty & \infty & 6& 0\end{array}\right)$
2. ②$\left(\begin{array}{ccccc}0& 3& 8& \infty & -4\\ \infty & 0& \infty & 1& 7\\ \infty & 4& 0& \infty & \infty \\ 2& \infty & -5& 0& \infty \\ \infty & \infty & \infty & 6& 0\end{array}\right)$
3. ③$\left(\begin{array}{ccccc}0& 3& 8& 4& -4\\ \infty & 0& \infty & 1& 7\\ \infty & 4& 0& 5& 11\\ 2& 5& -5& 0& -2\\ \infty & \infty & \infty & 6& 0\end{array}\right)$
4. ④$\left(\begin{array}{ccccc}0& 1& -3& 2& -4\\ 3& 0& -4& 1& -1\\ 7& 4& 0& 5& 3\\ 2& -1& -5& 0& -2\\ 8& 5& 1& 6& 0\end{array}\right)$

선지를 골라 바로 채점해 보세요.정답 보기

출처: 인사혁신처 공개 기출(공공데이터포털, 이용허락 제한 없음)