알고리즘 공부방

다익스트라 알고리즘은 그래프에서의 최단 거리를 구하는 알고리즘이다. 기본적으로 너비 우선 탐색과 비슷한 방법으로 작동한다. 사실, 너비 우선 탐색은 다익스트라에서 모든 간선의 길이가 1인 특수한 경우라고 봐도 된다. 다익스트라 알고리즘은 하나의 시작점으로부터 다른 모든 정점까지의 최단경로를 계산한다. 여기선 너비우선탐색과는 다르게, 지금까지 큐에 넣은, 우선순위 큐(Priority Queue를 이용하여) 방문할 정점들 중 가장 거리가 짧은 정점을 골라 그곳을 방문한다. 여기서 중요한 점은 bfs에서는 vis check 를 큐에 넣기 직전, 즉 실제로는 방문하지 않았지만, 발견 되었고, 곧 방문할 정점에 표시해 준다. 즉, 큐에 한번이라도 들어가기 위해선 vis check 를 해줘야 다른 정점이 이 정점을..