Dijkstra Algorithm (다익스트라 알고리즘)

https://www.youtube.com/watch?v=_lHSawdgXpI : 직관적 이해 도와주는 3분짜리 영상

https://code.google.com/archive/p/eclipselu/downloads : algorithm.pdf의 Dijkstra algorithm 부분 (Pseudocode 출처)

아래 그림의 파란색 한글 글씨 출처는 나

 

Pseudocode

 

이 수도코드에서는 dist가 업데이트될 때마다 priority queue H에 push 해주는 것이 아니라, 처음부터 H에 모든 원소에 대한 정보를 넣어주고 dist가 업데이트되면 H에도 그를 알린다는 컨셉이다. 이미 방문한 노드는 H에서 사라지므르 unvisited 라는 셋을 사용할 필요가 없는 것이다.

 

하지만 실제 구현할 때 dist가 업데이트된 것을 H에 알리려면 (가령 v의 dist가 업데이트되었다고 친다면) H에서 value가 v인 원소를 찾고, 그 원소의 key를 새로운 dist로 바꿔줘야 한다. 그러나 STL의 priority_queue는 내부 원소를 traverse 하도록 짜여있지도 않으므로 value가 v인 원소를 찾고 key를 바꿔주는 것 자체가 어렵다.

 

따라서 dist가 업데이트될 때마다 H에 push 하고, H에서 delete_min() 한 결과가 이미 방문한 노드의 정보라면 무시하는 방법을 쓸 수 있다. 이 때는 unvisited 라는 셋을 두고 delete_min() 한 결과가 방문한 노드인지, 아직 방문하지 않은 노드인지를 확인하고, 이번에 방문하였다면 unvisited에서 제거하는 방법을 쓸 수 있다.