다익스트라 관련하여 다시 질문 올립니다.

예전에 다익스트라 관련하여 질문올렸던 사람입니다.
kldp에서 도움을 받아 어찌어쬐 완성을 하기는 하였는데 조금더 모르는 것이 생겨 다시 질문올려봅니다.
질문의 맥락을 확실히하기위해 전에 올렸었던 글을 복사해왔습니다.
실질적인 질문은 RE: RE: RE: RE: 부분입니다.
이전에 답변해주신 분의 아이디는 블라인드 처리하였습니다.

원글

현재 프림, 크루스칼 알고리즘을 공부하고 다익스트라 알고리즘을 공부중입니다.
프림, 크루스칼 알고리즘의 개선을 위해 우선순위 큐를 사용하여 개선해보앗습니다.
다익스트라 알고리즘을 공부 도중 다익스트라 알고리즘도 우선순위 큐를 이용하여 개선이 된다는 이야기를 들었습니다.
그런데 도무지 다익스트라 알고리즘이 우선순위 큐를 통해 무엇이 개선되는지를 모르겠습니다.
저의 짧은 생각으로는
프림 알고리즘에서 
우선순위 큐는 각각의 단계에서 최소 간선의 정점을 삽입하고 정점을 '방문했음'으로 표시함으로서
실제로 큐의 총 enqueue,dequeue 연산을 줄여서 실행속도를 개선시킨다.
('방문했음' 정점은 우선순위 큐에 enqueue 하지 않음으로.)
크루스칼 알고리즘에서
우선순위큐는 각각의 간선의 가중치가 모두 오름차순으로 정렬됨으로서
이후 최소값을 찾는데에 별도의 비용이 발생하지 않아 실행속도를 개선시킨다.
라고 결론 내리고 있습니다.
그런데 제가 참고중인 알고리즘 서적 및 인터넷 자료에서 볼때,
다익스트라 알고리즘은 굳이 최소 거리에 있는 정점부터 조사해야될 필요가 없어 보입니다.
최소거리에 있는 정점부터 조사해야할 필요를 알면 우선순위 큐가 도임된 이유를 알 수 있을것 같습니다.
다익스트라 알고리즘에서 최소거리에 있는 정점부터 조사해야되는 이유는 무었인가요?
크게, 다익스트라 알고리즘에 우선순위 큐가 사용되는 이유는 무었인가요?

RE:

결국 모든 edge 에 대하여 조사한것이고, 우선순위큐를 사용하더라도 순서만 다를 뿐 조사 횟수에 차이가 없는 것같습니다
node와 egde가 많아 지면 연산량은 엄청나게 됩니다. 어차피 목적은 최단거리(shortest path)를 구하는 것이죠. 제일 짧은 놈을 골라서 처리하다가 goal이 나오면 그게 바로 답이 됩니다.

RE: RE:

우선 진심으로 답변 감사드립니다.
******님의 말씀은 우선순위 큐를 이용하여 최소 간선을 연결해 나가다가
주어진(혹은 사용자가 입력한) 목표 vertex를 만나면 종료한다는 말씀인것 같습니다.
(잘못 이해한 부분이 있다면 말씀해 주십시오.)
설명 덕분에 시작정점과 종료정점이 주어졌을 때 우선순위 큐를 이용하는 이유를 알거 되었습니다.
하지만 제가 공부하고 있는 책에서는 
다익스트라에 시작정점만을 주어주고 도착점을 나머지 모든 정점으로 정의하고 있습니다.
이런경우에도 우선순위큐의 도입이 필요한가요?

RE: RE: RE:

> ******님의 말씀은 우선순위 큐를 이용하여 최소 간선을 연결해 나가다가 주어진(혹은 사용자가 입력한) 목표 vertex를 만나면 종료한다는 말씀인것 같습니다. (잘못 이해한 부분이 있다면 말씀해 주십시오.)
네, 맞습니다.
> 하지만 제가 공부하고 있는 책에서는 다익스트라에 시작정점만을 주어주고 도착점을 나머지 모든 정점으로 정의하고 있습니다. 이런경우에도 우선순위큐의 도입이 필요한가요?
시작 node를 제외한 다른 모든 node들에 대한 cost를 모두 구하여야 한다는 말씀이신가요? 이같은 경우에는 다익스트라 알고리즘을 이용하여 계속해서 작업을 해 나가다가(cost가 작은 놈들을 우선으로 처리) 모든 node들에 대한 cost가 결정이 다 났을 때 작업을 종료해 주면 됩니다.

RE: RE: RE: RE:

******님의 말씀을 참고하여 다익스트라 알고리즘을 완성했습니다. ^^
감사합니다.
그런데 공부도중 딱 하나 더 모르는게 생겨 혹시나 하는 마음에 글올려봅니다 ㅠㅠ
"node와 egde가 많아 지면 연산량은 엄청나게 됩니다. 어차피 목적은 최단거리(shortest path)를 구하는 것이죠. 제일 짧은 놈을 골라서 처리하다가 goal이 나오면 그게 바로 답이 됩니다."
라고 말씀해 주셨는데, 이 말씀이
A->B (weight : 8)
B->C (weight : 100)
C->D (weight : 999)
A->D (weight : 1000)
과 같은 그래프에서 적용이 가능한가요??ㅠㅠ
머릿속으로 돌려보니 우선순위큐로 최소 가중치를 찾아 연결하는것을 반복하다가 goal을 만나 종료한다면
A->D (weight : 1000) 이 아니라 A->D (weight : 1099)로 연결되는 것 같습니다..ㅠㅠ
답변 기다립니다. ㅠ