이렇게 생각하시면 조금 더 수월하지 않을까요?
시작점은 x라고 가정합시다. 그리고 우선순위 큐에는 x에서부터 loc까지의 거리가 들어 있습니다.
여기에는 거리가 짧은 순서대로 저장이 되어 있겠지요.
- 우선순위 큐의 top에 x에서 a까지 가는 경로의 거리가 d라는 게 들어있었다.
고 가정해 봅시다.
(1) x에서 a까지 가는 경로는 d보다 짧아질 수 있을까요?
아뇨. 우선순위 큐에는 d보다 크거나 같은 것들만 저장되어 있습니다. 만약에, x에서 a까지 가는 경로의 거리가 d다.
라는 정보를 가진 item을 뺀 후에 x에서 a까지 가는 경로가 d보다 짧아지려면
어디에선가는 음수의 가중치가 반드시 존재해야 하겠지요.
(2) x에서 r을 거쳐서 a로 가는 게 더 빠를 수도 있지 않을까요?
만약에 x에서 r까지 가는 최단 거리가 d보다 작았다고 가정해 봅시다. (크다면 당연히 안 되고요.)
그리고 r에서 a까지 인접하다고 해 봅시다.
우선순위 큐에 이것까지 고려한 'a까지의 최단 거리'가 안 들어갔을까요?
만약에 그 거리가 d보다 작은 d'였다면, 이미 a까지 최단거리는 d'이 되었겠지요.
하지만, 최단 거리가 d였다는 소리는, 그 전에 a까지의 최단 경로에 대한 정보가 우선 순위 큐의 top에 안 올라왔다는 것입니다.
댓글을 작성하려면 로그인해야 합니다.
minhas2 6년 전
문제에 관련된 질문은 아닌데 다익스트라를 구현해보다가 궁금한점이 생겼습니다..
다익스트라 구현할때 어떤 시작정점을 택하고, 그 시작정점에 이어진 정점들중
그까지의 거리 가중치값이 가장 짧은 정점을 택해서 다시 탐색하는식인걸로 알고 있습니다.
그런데 왜 궂이 가장짧은 정점을 택하는지 모르겠습니다..
어차피 너비우선탐색이기 때문에 모든 정점을 방문할태고, 거리값을 비교해갈탠데
오히려 거리값이 가장짧은 정점을 일일이 탐색하는 과정이 시간낭비아닌가요?
제가 다익스트라를 잘못이해한건지,,,ㅜㅜ