수다닷컴

질문 제목 : 질문 내용 :

b[k]가 1이면 시작 노드에서 k노드로 가는 경로가 최종 확정된 최단경로, 0이면 아직 탐색중인 경로
dist[k] 가 시작 노드에서 k 노드로 가는 최단경로라고 했을 때,
힙의 이용이 어떻게 되는건지 궁금합니다. 또 다익스트라 기본적인 개념도 ㅡ,.ㅡ; 일부 궁금합니다.

초기값

disk 배열
0 4 2 9999
b 배열
1 0 0 0

루틴을 한번 돌아서
3 노드를 거쳐서 가는 경로를 구하면

disk 배열
0 4 2 7
b 배열
1 0 1 0

이 맞나요? k 노드를 거쳐서 가는 경로를 확인했을때. 시작 노드에서 k 노드로 가는 경로를 확정짓는건가요?그리고 우선순위큐에는 pairint, int나 구조체 형태로 (노드 id, 경로 비용)을 넣고 경로 비용이 최소가 되도록 넣고.

다음 루틴에서는 disk 배열에서 확정되지 않은 숫자 중 제일 작은건 2 노드이기 때문에
2 노드를 거쳐서 가는 경로를 구하면

disk 배열
0 4 2 5
b 배열
1 1 1 0

이 되겠네요.

여기서 또 큐에 (4, 5)를 넣게 되는데

그럼 이 시점에서 큐는
(4, 5) (4, 7)이 있는데 우선순위 조건에 따라 (4, 5)가 먼저 나오겠죠?
그 루틴을 돌고 난 후에는

b 배열이
1 1 1 1이 될테고,
다음에 나오는 (4, 7)은 b 배열을 봤을때 확정된 경로가 이미 있으니까 그냥 패스하고 다음 원소를 뽑아 처리하면 되는건가요?(다음 원소가 있다고 가정했을 때)
다익스트라 알고리즘을 알고 있었다고 생각했었는데, 참 ㅡ,.ㅡ; 힘드네요.

설명이 괜히 어렵게 된거 같은데, 제가 생각하고 있는 것이 맞는지 봐주세요.

신청하기