minhas2   4년 전

문제에 관련된 질문은 아닌데 다익스트라를 구현해보다가 궁금한점이 생겼습니다..

다익스트라 구현할때 어떤 시작정점을 택하고, 그 시작정점에 이어진 정점들중

그까지의 거리 가중치값이 가장 짧은 정점을 택해서 다시 탐색하는식인걸로 알고 있습니다.

그런데 왜 궂이 가장짧은 정점을 택하는지 모르겠습니다..

어차피 너비우선탐색이기 때문에 모든 정점을 방문할태고, 거리값을 비교해갈탠데

오히려 거리값이 가장짧은 정점을 일일이 탐색하는 과정이 시간낭비아닌가요?

제가 다익스트라를 잘못이해한건지,,,ㅜㅜ

gallopsys   4년 전

사실 어떻게 보면 틀린 생각을 하고 계신 건 아닙니다. Dijkstra 알고리즘은 기본적으로 Breadth First를 바탕으로 하고 있기 때문에 가중치가 낮은 간선을 찾기 위해 모든 정점을 탐색하는 과정은 정말 불필요한 과정일지도 모르지요.

하지만 모든 알고리즘의 바탕은 "원하는 결과값"을 얻음에 있습니다. Dijkstra 알고리즘도 이러한 바탕을 기초로 두고 있기 때문에 어쩔 수 없는 것이라 생각해요.
물론 Dijkstra 알고리즘만 있는 것이 아니라, SPFA(Shortest Path Faster Algorithm)와 같은 알고리즘도 있으니 한 번 공부해보시는 걸 추천드립니다.

minhas2   4년 전

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

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

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

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

gallopsys   4년 전

아뇨, 왜 굳이 가중치 값이 가장 짧은 걸 선택하는지 모르시겠다고 하셔서 덧붙인 말이었습니다. 물론 더 좋은 방법이 있으면 그걸로 풀어보셔도 좋아요. (물론 그 알고리즘이 정확한 값을 내놓는다는 가정 하에서 말이죠.)
제가 알기론 Dijkstra 알고리즘 같은 경우, 짧은 정점을 선택하더라도 그게 최단 거리임을 보장할 수 없으므로(정점 여러개를 거치는 편이 오히려 더 최단거리일 수 있으므로) 계속해서 값을 갱신해나가야 하는 구조라 정점을 여러 번 탐색하는 건 어쩔 수가 없거든요.

SPFA 알고리즘은 어떻게 보면 Dijkstra 알고리즘의 탐색을 조금이나마 줄여보려고 만든 알고리즘이라 할 수 있습니다. Dijkstra 알고리즘은 최단거리의 정점을 방문할 때 Queue나 Priority queue에 바로 추가하는 반면, SPFA 알고리즘은 Queue에 있는 값을 갱신시키는 구조거든요. Hash Table에 대해서 공부하셨다면 좀 더 빠르게 길찾기를 하실 수 있는 알고리즘으로 알고 있습니다.

minhas2   4년 전

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

jh05013   4년 전

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

chogahui05   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에 안 올라왔다는 것입니다.

댓글을 작성하려면 로그인해야 합니다.