[Python] 최단 경로 - 다익스트라(Dijkstra) 알고리즘 구현하기

다익스트라(Dijkstra) 알고리즘은 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘이다. 다익스트라 알고리즘의 시간복잡도는 O(E)+O(ElogE)=O(ElogE)이다.

다익스트라 알고리즘에서는 방문하지 않은 인접 노드를 탐색할 때 우선순위 큐를 사용한다. 그 이유는 지금까지 발견된 가장 가까운 거리의 노드를 먼저 계산할 수 있기 때문이다. 가장 가까운 정점을 계산해 놓으면 그보다 더 먼 거리의 경로에 대해서는 고려할 필요가 없어진다. 우선순위 큐는 heapq 모듈을 이용해 구현할 수 있다.

다익스트라 알고리즘 프로세스

1. 시작 정점을 결정한다.
2. 시작 정점에서 각각 다른 정점까지의 거리 값을 무한대로 초기화한다.
   (시작 정점이 a라면, distance[b] = a->b의 거리를 뜻함)
   시작 정점 -> 시작 정점은 0으로 초기화한다.
3. 시작 정점을 우선순위 큐(=미방문 집합)에 삽입하고 시작한다.
4. 방문하지 않은 정점이 있다면(len(우선순위 큐) > 0), 큐에서 꺼내 해당 정점에서 방문하지 않은 인접 정점들을 탐색한다.
   기존에 저장되어 있는 인접 정점까지의 거리(distance[a])보다 현재 정점을 거쳐 인접 정점에 도달하는 거리가 더 짧을 경우 짧은 거리로 갱신해준다.
5. 다음 인접 거리를 계산하기 위해 갱신한 정점을 우선순위 큐에 삽입한다.
6. 4~5번의 과정을 방문하지 않은 정점이 없을 때까지 반복한다.

시작점이 A일 때, d[A]만 0으로 놓고 나머지는 무한대로 설정한다. S는 방문한 노드의 집합이고, Q는 방문하지 않는 노드의 집합이다. 파이썬 코드에서는 Q를 우선순위 큐로 거리까지 함께 저장해 사용할 것이다.

시작점 A의 인접 정점들을 탐색하며, d[노드]에 저장되어 있는 값보다 정점 A를 거쳐 가는 값이 더 작을 경우 그 값으로 업데이트한다. 여기서는 모두 INF 무한대 값보다 작기 때문에 연결된 인접 정점을 모두 업데이트하게 된다.

정점 B의 인접 정점들을 탐색한다. 역시 무한대 값보다 무조건 작기 때문에 d[E]를 업데이트하게 된다.

계속해서 방문하지 않은 노드가 없을 때까지 반복해준다. 현재 정점을 거쳐 인접 정점으로 가는 것이 더 비용이 적게 들 때 d리스트의 값을 업데이트해준다. 그림에서는 정점 C로 갈 때, 시작점 A에서 바로 C로 가는 것(30)보다 A -> D -> C를 거쳐서 가는 것(20)이 더 빠르기 때문에 d[C]를 업데이트해 주었다. 마찬가지로 A -> C -> F보다 A -> D -> C -> F가 더 빠르기 때문에 d[F]값을 업데이트해 주었다.

다익스트라 구현 코드(Python)

참고 링크

다익스트라 알고리즘 - 나무위키
Python으로 다익스트라(dijkstra) 알고리즘 구현하기