다익스트라 알고리즘에서 우선순위큐를 사용하는 이유가 궁금합니다.
글쓴이: canuyes / 작성시간: 화, 2013/03/19 - 10:43오전
현재 프림, 크루스칼 알고리즘을 공부하고 다익스트라 알고리즘을 공부중입니다.
프림, 크루스칼 알고리즘의 개선을 위해 우선순위 큐를 사용하여 개선해보앗습니다.
다익스트라 알고리즘을 공부 도중 다익스트라 알고리즘도 우선순위 큐를 이용하여 개선이 된다는 이야기를 들었습니다.
그런데 도무지 다익스트라 알고리즘이 우선순위 큐를 통해 무엇이 개선되는지를 모르겠습니다.
저의 짧은 생각으로는
프림 알고리즘에서
우선순위 큐는 각각의 단계에서 최소 간선의 정점을 삽입하고 정점을 '방문했음'으로 표시함으로서
실제로 큐의 총 enqueue,dequeue 연산을 줄여서 실행속도를 개선시킨다.
('방문했음' 정점은 우선순위 큐에 enqueue 하지 않음으로.)
크루스칼 알고리즘에서
우선순위큐는 각각의 간선의 가중치가 모두 오름차순으로 정렬됨으로서
이후 최소값을 찾는데에 별도의 비용이 발생하지 않아 실행속도를 개선시킨다.
라고 결론 내리고 있습니다.
그런데 제가 참고중인 알고리즘 서적 및 인터넷 자료에서 볼때,
다익스트라 알고리즘은 굳이 최소 거리에 있는 정점부터 조사해야될 필요가 없어 보입니다.
최소거리에 있는 정점부터 조사해야할 필요를 알면 우선순위 큐가 도임된 이유를 알 수 있을것 같습니다.
다익스트라 알고리즘에서 최소거리에 있는 정점부터 조사해야되는 이유는 무었인가요?
크게, 다익스트라 알고리즘에 우선순위 큐가 사용되는 이유는 무었인가요?
Forums:
...
A에서 X까지의 거리를 구한다고 할 때,
A->B (distance 10)
B->C (distance 10)
C->D (distance 10)
......
W->X (distance 10)
A->Y (distance 1)
Y->Z (distance 1)
Z->B (distance 1)
거리순이 아닌 알파벳 순으로 탐색을 하면 어떤 일이 일어날지 생각해 보세요.
답글 남깁니다.
답변 감사합니다.
말씀해주신 그래프를 그림으로 그려서 확인해 보았습니다.
우선 A에서 알파벳순으로 경로의 길이가 B부터 10,20,30.....과 같이 갱신되리라 생각합니다.
그런데 그 이후에 B~X는 각각 하나의 인접 정점 밖에 가지고 있지 않음으로
결국 마지막에 A의 B가 아닌 또 다른 인접 정점인 Y에서
A->Y : 1
A->Z ：2
A->B :3
으로 다시 갱신되어 올바른 출력을 보일것이라 생각합니다.
결국 모든 edge 에 대하여 조사한것이고,
우선순위큐를 사용하더라도 순서만 다를 뿐 조사 횟수에 차이가 없는 것같습니다.
분명 제가 틀린 생각을 하고 있는 것 같은데 어느 부분이 틀린지 모르겠습니다.
한번만 더 조언을 구합니다.
gilgil.net
> 결국 모든 edge 에 대하여 조사한것이고, 우선순위큐를 사용하더라도 순서만 다를 뿐 조사 횟수에 차이가 없는 것같습니다
node와 egde가 많아 지면 연산량은 엄청나게 됩니다. 어차피 목적은 최단거리(shortest path)를 구하는 것이죠. 제일 짧은 놈을 골라서 처리하다가 goal이 나오면 그게 바로 답이 됩니다.
www.gilgil.net
답글 남깁니다.
우선 진심으로 답변 감사드립니다.
gilgil님의 말씀은 우선순위 큐를 이용하여 최소 간선을 연결해 나가다가
주어진(혹은 사용자가 입력한) 목표 vertex를 만나면 종료한다는 말씀인것 같습니다.
(잘못 이해한 부분이 있다면 말씀해 주십시오.)
설명 덕분에 시작정점과 종료정점이 주어졌을 때 우선순위 큐를 이용하는 이유를 알거 되었습니다.
하지만 제가 공부하고 있는 책에서는
다익스트라에 시작정점만을 주어주고 도착점을 나머지 모든 정점으로 정의하고 있습니다.
이런경우에도 우선순위큐의 도입이 필요한가요?
> gilgil님의 말씀은 우선순위 큐를 이용하여
> gilgil님의 말씀은 우선순위 큐를 이용하여 최소 간선을 연결해 나가다가 주어진(혹은 사용자가 입력한) 목표 vertex를 만나면 종료한다는 말씀인것 같습니다. (잘못 이해한 부분이 있다면 말씀해 주십시오.)
네, 맞습니다.
> 하지만 제가 공부하고 있는 책에서는 다익스트라에 시작정점만을 주어주고 도착점을 나머지 모든 정점으로 정의하고 있습니다. 이런경우에도 우선순위큐의 도입이 필요한가요?
시작 node를 제외한 다른 모든 node들에 대한 cost를 모두 구하여야 한다는 말씀이신가요? 이같은 경우에는 다익스트라 알고리즘을 이용하여 계속해서 작업을 해 나가다가(cost가 작은 놈들을 우선으로 처리) 모든 node들에 대한 cost가 결정이 다 났을 때 작업을 종료해 주면 됩니다.
www.gilgil.net
답글 남깁니다.
진심으로 답변 감사드립니다.
gilgil님이 일러주신것을 참고하여 한번 시도해보겠습니다.
행복한 하루되세요 ^^
gilgil.net
네, 수고하세요. ^^
www.gilgil.net
답글 남깁니다.
gilgil님의 말씀을 참고하여 다익스트라 알고리즘을 완성했습니다. ^^
감사합니다.
그런데 공부도중 딱 하나 더 모르는게 생겨 혹시나 하는 마음에 글올려봅니다 ㅠㅠ
"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)로 연결되는 것 같습니다..ㅠㅠ
답변 기다립니다. ㅠ
맞아요
골을만난다고 종료하는게 아닙니다 윗분의 방법은 편법으로 가능하나 항상 바른 해를 기대할순없습니다 다익스트라는 넓이우선 알고리즘중하나입니다 항상 바른해를 찾습니다 큐를 사용하면 한노드가 업데이트 됬을때 그에 연결되서 발견됐다는 노드를 다시 큐에 넣어야 하나 우선순위는 그러지 않아도 됩니다
댓글 달기