다음 방향 그래프의 a 노드에서 각 노드별 최단 경로를 다익스트라(Di… | [7급 국가직 알고리즘] 23년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 23년 1회차
다음 방향 그래프의 a 노드에서 각 노드별 최단 경로를 다익스트라(Dijkstra) 알고리즘으로 계산할 때, 각 노드별 최단 거리 갱신 횟수로 옳은 것은? (단, a 노드를 제외한 모든 노드의 최단 경로 초기값은 ∞이다)
1
b : 1회, c : 1회
2
f : 2회, g : 1회
3
d : 2회, i : 2회
4
e : 3회, h : 1회
해설
갱신 횟수가 옳은 것은 e 3회, h 1회이다.
a(0) 확정: b=2, e=11, d=13
b(2) 확정: c=10, e=9, f=5
f(5) 확정: c=6, i=6
c(6)·i(6) 확정: h=7, e=8
h(7) 확정: d=11, g=8
e(8)·g(8) 확정: d=10∞에서 처음 값이 들어가는 것도 갱신으로 세면 e는 ∞→11→9→8로 3회, h는 ∞→7로 1회다.
- b·c 조합: c는 ∞→10→6으로 2회 갱신된다.
- f·g 조합: f는 ∞→5로 1회만 갱신된다.
- d·i 조합: d는 ∞→13→11→10으로 3회, i는 ∞→6으로 1회다.
오류나 개정된 내용이 보이면 알려주세요