[7급 국가직 알고리즘 2025년 16번]

다음은 단일 출발점 최단 경로를 찾기 위한 다익스트라(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] = (가);
		}
	}
}