다음 그래프에는 음의 가중치가 존재한다. 이 그래프에서, 노드 A에서 … | [7급 국가직 자료구조론] 19년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 19년 1회차
다음 그래프에는 음의 가중치가 존재한다. 이 그래프에서, 노드 A에서 노드 F로의 최단 경로를 구하고자 할 때, 최소 비용은?
1
3
2
5
3
7
4
9
해설
노드 A에서 F까지의 최소 비용은 3이다.
F로 들어오는 간선은 E→F(−7)뿐이고, E는 G→E(4), G는 D→G(2) 또는 F→G로만 도달한다. 따라서 A에서 D까지의 최단 거리가 핵심이다.
음의 간선을 이용한 A→C→B→D가 9−15+10=4로 가장 짧다.
이어서 G=4+2=6, E=6+4=10, F=10−7=3이다. 순환 F→G→E→F의 합은 5+4−7=+2로 양수라 더 줄어들지 않는다.
- 9는 A→C→D(9+1=10)를 거친 값으로, 음의 간선 C→B(−15)를 활용한 더 짧은 경로를 놓친 결과이다(Dijkstra처럼 B를 먼저 확정해 버리면 이 값이 나온다).
오류나 개정된 내용이 보이면 알려주세요
