gallopsys님 답변 진심으로 감사드립니다

그런데 답변하신 내용중에서, 원하는 결과값을 얻음에 있다는 말씀은 제가 질문드린 방식이 잘못된값을 낼 가능성이 있다는 말씀이신가요?

그리고 가장 작은 토탈 가중치를 가진 정점을 탐색하는 과정이 그래프알고리즘의 기본적인 바탕이란 말씀이신건가요?

spfa잠깐 검색해봤는데 다익스트라의 상향된 알고리즘인가요? 다음번에 꼭 공부해보겠습니다 감사드립니다!

아 그렇군요..! 답변 감사드립니다! 헤쉬테이블 아직공부 안했는데 공부하면 꼭 구현해보겠습니다~~ㅎㅎ

다익스트라 알고리즘에서 다음 루프에 선택해야 할 정점은 "최단거리임이 확실한 정점"이고, 그 때까지 선택하지 않은 정점 중 거리값이 가장 작은 점이 바로 그 점입니다. 만약 v까지의 거리가 5이고 거기서 루프를 돌렸는데 이후에 계산해 보니 거리가 4였다면, 똑같은 루프를 한 번 더 돌려야겠죠.

이렇게 생각하시면 조금 더 수월하지 않을까요?

시작점은 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에 안 올라왔다는 것입니다.