저도 알고리즘 초보지만 알고있는대로 도움이 되시기를 바라며 답변을 드리자면, 느릴 수밖에 없다고 생각합니다.
왜냐하면 우선순위 큐= 힙 (최소 힙)을 사용하여서 짜면, 한번 들어간 값이 갱신될 확률이 당연히 일반 큐를 써서 짤때보다 낮을 수밖에 없습니다.
왜냐하면 항상 현재 간선들의 연결 상황에서 낮은 값을 선택 해놓으면 당연히 나중에 더 작은 값으로 갱신될 확률이 낮을 수밖에 없으니까요.
따라서 그 값들을 갱신하는 데서 시간이 차이가 날것입니다.
그리고 다익스트라 알고리즘은 bfs의 일종이라고 들었습니다. 당연히 큐(bfs)로 짜셔도 결과는 나올거라고 생각합니다.
lgun202 5년 전
아래의 코드는 단순히 큐 자료구조를 이용해 구현한 다익스트라 알고리즘인데요,
우선순위 큐로 구현한 다익스트라 알고리즘보다 느린가요?
다익스트라 문제 풀때는 항상 우선순위 큐로 구현하는게 좋을까요?