그래프에서 모든 정점 간의 최단 경로 비용을 구하기 위한 플로이드-워샬… | [7급 국가직 자료구조론] 10년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 10년 1회차
그래프에서 모든 정점 간의 최단 경로 비용을 구하기 위한 플로이드-워샬 알고리즘은 아래의 식으로 표현된다.위의 식에서 는 정점 에서 정점 로 가는 간선의 가중치를 나타내며, 는 보다 더 큰 인덱스를 갖는 정점을 통과하지 않으면서 에서 까지 갈 수 있는 최단 경로 비용을 나타낸다. 아래 그래프에 대해 행렬 의 값으로 알맞은 것은?
1
2
3
4
해설
는 정점 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 등이 아직 무한대인 행렬은 간선 가중치 그대로인 초기 행렬 이다.
- 4→2가 -1인 행렬은 4→3→2(-5+4) 경로를 반영한 것으로, 정점 3까지 경유를 허용해야 나오는 값이다.
- 모든 칸이 유한값으로 채워진 행렬은 정점 5까지 모두 경유를 허용한 최종 결과이다.
오류나 개정된 내용이 보이면 알려주세요
