[일반] 다익스트라 priorty queue로 구현할때 질문좀

[익명(14.37)]

이거 bfs로 구현하는거야?

근데 bfs 로 구현 하면

예를 들어 이번 단계에 인덱스 4랑 5가 기존 경로보다 더 짧은걸로 판명나서 둘다 큐에 추가된다 치면

다음 단계에서는 4를 거쳐가는 최소거리가 갱신되고 그다음에 5를 거쳐가는 최소거리가 갱신되는데

그러면 손해 아니야?

만약 4를 거쳐가는 최소거리를 구하는 과정에서 5를 거쳐가는게 무의미하다고 결론나면

괜히 이전단계에서 4만 넣어도 되는걸 5까지 넣어버려서

쓸데없는 검증을 하는거잖아

[익명(121.142)]

내가보기엔 dijkstra 이론을 다시 보고 오는게 맞아보인다

[익명(121.142)]

5를 거쳐가는게 무의미하다고 그 5로 가는게 최단거리일 수도 있자나

[익명(14.37)]

설명 잘 못한거같은데 잘 답변해줬네 다시 알아볼게 ㄳ

[익명(14.37)]

그러면 그냥 vector로 구현하는거랑 priorty_queue로 구현하는거랑 뭔가 구현 방향이 크게 다른 것 같은데 맞아?

[익명(14.37)]

그리고 v^2 < e 일 경우 그냥 벡터로 하는게 이득이지?

[익명(121.142)]

vector로 구현한다하면 최솟값들 어떻게 관리할거임?? 무조건 pq가 낫지 않나

[익명(14.37)]

아니네 구현방향 비슷하네 ㅅㅂ 헷갈린다

[익명(121.142)]

이게 최솟값들을 계속 관리를해줘야하자나 거리가 최소인 정점으로 계속 이동해줘야하는데 이렇게 거리 갱신하다보면 최솟값이 계속 변하게 되고

[익명(121.142)]

그래서 priority_queue로 최솟값들 관리해주는거

[익명(14.37)]

ㄳㄳ

[Gravekper(gravekper)]

큐에는 갱신될 때마다 아무튼 계속 넣음. 운 나쁘면 최대 |E|개까지 들어감. 큐에 들어있는 값이 의미있는 값인지 어떤지는 꺼낼 때 판별해야 함.

[Gravekper(gravekper)]

이것도 읽어보면 좋다
https://www.secmem.org/blog/2019/01/09/wrong-dijkstra/

[익명(14.37)]

ㄳㄳ