Dijstra 알고리즘 - python

문제를 풀다 보면 최단 경로와 관련한 문제들이 종종 출제된다.

물론 bfs나 dfs와 같은 완전탐색이 필요한 경우도 있지만, 대부분 다익스트라 알고리즘으로 해결이 가능하다.

 

Dijstra 알고리즘은 기본적으로 최단 경로를 찾는 알고리즘이다. 즉 출발 노드로 부터 각 노드들의 최단 거리를 구할 수 있고, 경로 또한 계산이 가능하다. 주의할 점은 다익스트라는 양의 weight를 가지는 edge들이 있다는 가정이 필요하다.

 

기본적인 로직은 다음과 같다.
1. 출발 노드를 방문.
2. 해당 노드로 부터 연결된 노드들을 통해 각 노드들 마다 거리를 계산 후 저장.
3. 방문하지 않은 노드들 중 출발 노드랑 거리가 가장 작은 노드에 방문.
4. 새로 방문한 경로를 통해 계산된 새로운 거리와 기존에 저장된 최단 거리 비교해 작은 값으로 업데이트.
5. 3 ~ 4번 반복
6. 더 이상 방문할 노드가 없다면, 저장된 값들이 각 노드들까지의 최소 거리를 의미한다.

 

 

해당 로직을 이용해 그대로 코드로 작성했다.

(백준 1916번: 최소비용 구하기)

 

하지만 priority queue를 이용하면 다른 방식으로도 구현이 가능하다.

기존에는 방문하지 않은 노드들을 따로 저장해 관리해주었고, 해당 노드들 중에 최단 거리를 가지는 노드를 방문하도록 했다. 하지만 이를 pq를 이용해 최소 거리를 가진 다음 노드를 방문하는 방식으로 해결이 가능하다.

(백준 1916번: 최소비용 구하기)

 

 

 

첫 번째 코드가 좀 더 로직에 직관적이지만, 실제 구현과 효율성을 따진다면 pq가 유리하다.