p_ce1052   9달 전

아직 방문 안된 점 중 시작점으로부터의 거리가 최소인 점을 계속 찾기 위해 우선순위 큐를 이용하잖아요?근데 우선순위 큐에 들어가 있는 동안 거리값이 바뀌어버리면 어떻게하나요? 큐 내에서 실시간으로 업데이트 해줘야되나요?

djm03178   9달 전

바꾸지 않아도 됩니다. 바뀐 정보를 한 번 더 push만 해도 됩니다. 엄밀히 말하면 시간 복잡도가 O((V+E)logE)인가 O((V+E)logV)인가의 차이는 있지만, 크게 문제가 될 정도로 효율성이 달라지는 일은 거의 없습니다.

이렇게 해도 되는 이유는, 해당 정점이 처음으로 큐에서 나왔을 때의 거리만이 중요하고 그 이후에 나오는 것들은 오래된 정보이므로 그대로 버리면 되기 때문입니다.

p_ce1052   9달 전

아 같은 정점이 두개 들어가있어도 상관 없겠군요 어자피 최솟값이 빠져나와서 visited표시되겠네요 감사합니다

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