lgun202   5년 전

아래의 코드는 단순히 큐 자료구조를 이용해 구현한 다익스트라 알고리즘인데요,

우선순위 큐로 구현한 다익스트라 알고리즘보다 느린가요?

다익스트라 문제 풀때는 항상 우선순위 큐로 구현하는게 좋을까요?

Rose   5년 전

저도 알고리즘 초보지만 알고있는대로 도움이 되시기를 바라며 답변을 드리자면, 느릴 수밖에 없다고 생각합니다.

왜냐하면 우선순위 큐= 힙 (최소 힙)을 사용하여서 짜면, 한번 들어간 값이 갱신될 확률이 당연히 일반 큐를 써서 짤때보다 낮을 수밖에 없습니다. 

왜냐하면 항상 현재 간선들의 연결 상황에서 낮은 값을 선택 해놓으면 당연히 나중에 더 작은 값으로 갱신될 확률이 낮을 수밖에 없으니까요.

따라서 그 값들을 갱신하는 데서 시간이 차이가 날것입니다.

그리고 다익스트라 알고리즘은 bfs의 일종이라고 들었습니다. 당연히 큐(bfs)로 짜셔도 결과는 나올거라고 생각합니다.

Green55   5년 전

우선순위 큐를 사용하지 않으면 O(V^2), 사용할 시에는 O(ElgV)의 시간 복잡도를 갖게 됩니다.

일반적으로 ElgV의 시간복잡도가 더 앞서는 경우가 많아서 우선순위 큐를 이용한 다익스트라를 사용하는 경우가 많지만,

완전 그래프, 즉 E = V^2인 그래프가 주어지는 문제에서는 보통 전자가 더 빠르기 때문에 우선순위 큐를 사용하지 않기도 합니다.

lgun202   5년 전

아.. 그렇군요 감사합니다!!

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