바꾸지 않아도 됩니다. 바뀐 정보를 한 번 더 push만 해도 됩니다. 엄밀히 말하면 시간 복잡도가 O((V+E)logE)인가 O((V+E)logV)인가의 차이는 있지만, 크게 문제가 될 정도로 효율성이 달라지는 일은 거의 없습니다.
이렇게 해도 되는 이유는, 해당 정점이 처음으로 큐에서 나왔을 때의 거리만이 중요하고 그 이후에 나오는 것들은 오래된 정보이므로 그대로 버리면 되기 때문입니다.
댓글을 작성하려면 로그인해야 합니다.
p_ce1052 3년 전