그래프에서 모든 정점 간의 최단 경로 비용을 구하기 위한 플로이드-워샬… | [7급 국가직 자료구조론] 10년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 10년 1회차
그래프에서 모든 정점 간의 최단 경로 비용을 구하기 위한 플로이드-워샬 알고리즘은 아래의 식으로 표현된다.
Ak[i][j]=min⁡{Ak−1[i][j], Ak−1[i][k]+Ak−1[k][j]}, k>0A^k[i][j]=\min\{A^{k-1}[i][j],\ A^{k-1}[i][k]+A^{k-1}[k][j]\},\ k>0
A0[i][j]=cost[i][j]A^0[i][j]=\mathrm{cost}[i][j]
위의 식에서 cost[i][j]\mathrm{cost}[i][j]는 정점 ii에서 정점 jj로 가는 간선의 가중치를 나타내며, Ak[i][j]A^k[i][j]는 kk보다 더 큰 인덱스를 갖는 정점을 통과하지 않으면서 ii에서 jj까지 갈 수 있는 최단 경로 비용을 나타낸다. 아래 그래프에 대해 행렬 A2A^2의 값으로 알맞은 것은?
문제 이미지
1
(0384−4∞0∞17∞405112−1−50−2∞∞∞60)\begin{pmatrix}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{pmatrix}
2
(038∞−4∞0∞17∞40∞∞2∞−50∞∞∞∞60)\begin{pmatrix}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{pmatrix}
3
(0384−4∞0∞17∞4051125−50−2∞∞∞60)\begin{pmatrix}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{pmatrix}
4
(01−32−430−41−1740532−1−50−285160)\begin{pmatrix}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{pmatrix}
해설

A2A^2는 정점 1, 2만 중간 정점으로 허용해 갱신한 행렬로, 4행이 (2, 5, -5, 0, -2)이고 1→4가 4, 3→4가 5, 3→5가 11인 행렬이다.

정점 1 경유: 1로 들어오는 간선은 4→1(2)뿐이므로 4→2=2+3=5, 4→5=2+(-4)=-2로 갱신된다.

정점 2 경유: 1→4=3+1=4, 3→4=4+1=5, 3→5=4+7=11로 갱신되고, 4→5는 5+7=12보다 기존 -2가 작아 유지된다.

  • 1→4, 4→2, 3→5 등이 아직 무한대인 행렬은 간선 가중치 그대로인 초기 행렬 A0A^0이다.
  • 4→2가 -1인 행렬은 4→3→2(-5+4) 경로를 반영한 것으로, 정점 3까지 경유를 허용해야 나오는 값이다.
  • 모든 칸이 유한값으로 채워진 행렬은 정점 5까지 모두 경유를 허용한 최종 결과이다.

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

이어서 풀어보기

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