jw030411   3년 전

자바로 다익스트라 공부를 하고 있는데요, 블로그 글들을 여럿 찾아보니까 우선순위 큐로 다익스트라를 구현했을때

방문을 했는지 안했는지 따지지 않는 경우가 많아서 왜 따지지 않아도 되는지 궁금합니다

invrtd_h   3년 전

pq에서 한번 x라는 값이 빠져나오면 이후에 그 pq에는 x 이하의 값이 다시는 들어오지 않기 때문입니다.

처음에 정답을 나타내는 배열 L이 [+inf] * n으로 init되어 있으며, 이후 알고리즘 수행 중 임의의 시점에 L을 살펴볼 때, L[v]의 값이

* pq의 top 원소보다 크면 v는 visiting이 끝나지 않은 vertex

* pq의 top 원소보다 작으면 v는 visiting이 끝난 vertex

입니다. 따라서 pq의 원소와 L[v]를 비교함으로써 visiting이 끝났는지 끝나지 않았는지를 판정할 수 있습니다. 그리고 pq에 들어오는 값은 pq의 top 원소 + edge weight이기 때문에, visiting이 끝난 vertex를 향하는 간선은 다시는 이 pq에 들어올 일이 없습니다.

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