다음은 단일 출발점 최단 경로를 찾기 위한 다익스트라(Dijkstra)… | [7급 국가직 알고리즘] 25년 1회차 기출문제 상세 페이지

다음은 단일 출발점 최단 경로를 찾기 위한 다익스트라(Dijkstra) 알고리즘을 의사(pseudo) 코드로 기술한 것이다. 이 코드에서 (가)에 들어갈 내용으로 옳은 것은?
// 입력: 가중 방향 그래프 G, 인접 행렬 A, 시작 정점 s
// 출력: s로부터 다른 모든 정점까지의 최단 경로의 길이
Dijkstra(G, A, s) {
    U = {s};
    for(모든 정점 v ∈ G)
        D[v] = A[s][v];
    while(U != G) {
        D[w]가 최소인 정점 w ∈ (G - U)를 선택
        U = U ∪ {w};
        for(w에 인접한 모든 정점 v) {
            D[v] = (가);
        }
    }
}

min(D[v], D[v] ＋ A[v][w])

min(D[v], D[w] ＋ A[v][w])

min(D[v], D[v] ＋ A[w][v])

min(D[v], D[w] ＋ A[w][v])

(가)에 들어갈 갱신식은 min(D[v], D[w] ＋ A[w][v])이다.
새로 확정된 정점 w를 거쳐 v로 가는 경로의 길이는 s에서 w까지의 최단 거리 D[w]에 간선 w→v의 가중치 A[w][v]를 더한 값이다. 이것이 기존 D[v]보다 작으면 갱신한다(완화).
D[v] ＋ A[v][w]는 w를 거치는 경로가 아니라 v에서 출발하는 값이라 의미가 없다.
D[w] ＋ A[v][w]는 방향 그래프에서 간선 방향을 v→w로 거꾸로 읽은 것이다.
D[v] ＋ A[w][v]는 w까지의 거리 대신 v의 거리를 더해 w를 경유하는 경로가 아니다.