[Python][이코테] 최단경로 / 다익스트라 알고리즘(2)

2022.11.09 - [Algorithm/이것이 코딩테스트다] - [Python][이코테] 최단경로 / 다익스트라 알고리즘(1)

 

개선된 다익스트라 알고리즘

기존의 간단한 다익스트라 알고리즘은 시간 복잡도가 \(O(V^2)\) 이다.

 

이번에 공부할 개선된 다익스트라 알고리즘은 \(O(ElogV)\)를 보장한다. (E = 간선의 개수, V = 노드의 개수)

 

간단한 다익스트라 알고리즘은 '최단 거리가 가장 짧은 노드'를 찾기 위해 매번 최단 거리 테이블을 선형적으로 탐색했다.

 

이 과정에서만 \(O(V)\)의 시간이 걸렸다.

 

하지만 개선된 알고리즘은 힙(Heap) 자료구조를 사용한다. 힙 자료구조를 사용하면 특정노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 가장 짧은 노드를 더욱 빠르게 찾을 수 있다. 이 과정에서는 선형 시간이 아닌 로그 시간이 걸린다.

 

힙 설명

힙 자료구조는 우선순위 큐(Priority Queue)를 구현하기위해 사용하는 자료구조이다. 

 

스택/큐와 비슷한데

 

자료구조	추출되는 데이터
스택	가장 나중에 삽입된 데이터
큐	가장 먼저 삽입된 데이터
우선순위 큐	가장 우선순위가 높은 데이터

 

파이썬에서 우선순위 큐를 사용하기 위해서는 PriorityQueue 혹은 heapq 라이브러리를 사용할 수 있다.

 

두 라이브러리 모두 우선순위 큐를 지원하지만 PriorityQueue 보다 heapq가 더 빠르게 동작하기 때문에 heapq를 권장한다.

 

우선순위 큐 사용

우선순위 큐를 구현할 때 내부적으로 '최소 힙(Min Heap)' 혹은 '최대 힙(Max Heap)'을 이용한다.

 

• 최소 힙 : 값이 낮은 데이터가 먼저 삭제
• 최대 힙 : 값이 큰 데이터가 먼저 삭제

파이썬 라이브러리는 기본적으로 최소 힙 구조를 이용하기 때문에 다익스트라 최단경로 알고리즘에서는 비용이 적은 노드를 우선 방문하므로 최소 힙 구조를 기반으로하는 파이썬의 우선순위 큐 라이브러리가 적합하다.

 

* 만약 최소 힙을 최대 힙처럼 사용하려면 일부러 우선순위 값에 (-)를 곱하여 음수로 만들어 넣었다가, 나중에 우선순위 큐에서 꺼낸 후 다시 음수부호를 붙여 양수로 만들어 사용하는 방식이 적용 가능하다.

 

개선된 다익스트라 알고리즘 구현

 

0. 초기 상태

간단한 다익스트라 알고리즘과는 구현방식이 살짝 다르다.

 

노드 번호와 거리를 튜플 형태로 저장한다. (거리, 노드번호) 식으로

 

(거리, 노드번호) 순서의 튜플로 저장 후 최소 힙을 사용하면 튜플의 첫 번째 원소를 기준으로 우선순위 큐를 구성한다. 따라서 (거리, 노드 번호) 순서대로 튜플 데이터를 구성해 우선순위 큐에 넣으면 거리순으로 정렬이 된다.

 

시작은 1번 노드부터 시작하며, 거리는 자기 자신이기 때문에 0

 

우선순위 큐

(거리:0, 노드:1)

 

 

1.

우선순위 큐에 (거리:0, 노드: 1)을 꺼낸다. 

 

우선순위 큐에는 항상 거리가 가장 짧은 튜플이 최상위 원소로 있기 때문에 그저 꺼내서 사용하면 된다.

 

후에 이미 방문한 노드가 있다면 무시하면 된다.

 

1번 노드를 꺼냈으므로 1번과 연결된 2번, 3번, 4번 노드로 가는 최소비용을 계산한다.

 

무한대와 거리를 비교하기 때문에 해당 값들이 더 적은값이므로 해당 거리들로 갱신된다.

 

이후 갱신한 정보들은 다시 우선순위 큐에 넣는다. 

 

우선순위 큐

(거리: 1, 노드: 4) (거리:2, 노드:2) (거리:5, 노드:3)

 

2.

이어서 다시 우선순위 큐에서 원소를 꺼내서 동일한 과정을 반복한다.

 

최상단 원소가 (거리:1, 노드: 4) 가 나온다. 

 

이후 노드 4를 기준으로 노드 4와 연결된 간선들을 확인한다.

 

4번노드를 거쳐 3번과 5번노드로 가는 최소비용은 4(1+3)과 2(1+1) 이므로 기존에 3으로 가는 거리 5보다 4가 작으며

 

5번은 아직 무한이기 때문에 둘다 4와 2로 갱신된다. 그 후 우선순위 큐에는 (거리:4, 노드:3) (거리:2, 노드:5)가 추가된다.

 

우선순위 큐

(거리:2, 노드:2) (거리:2, 노드:5) (거리:4, 노드:3) (거리:5, 노드:3)

 

3.

이번에는 우선순위 큐에서 (거리:2, 노드:2) 를 꺼낸다. 아직 방문하지 않았기에 2번 노드에 해당하는 간선들을 처리해준다.

 

2번노드에서 4번노드로 가는 거리는 4(2+2) 하지만 4번노드의 거리는 1이기 때문에 갱신되지 않으며

 

2번노드에서 3번노드로 가는 거리는 5(2+3) 하지만 3번 노드의 거리는 4이기 때문에 갱신되지 않는다.

 

그 어느것도 갱신되지 않았기 때문에 우선순위 큐에도 삽입되지 않는다.

 

우선순위 큐

(거리:2, 노드:5) (거리:4, 노드:3) (거리:5, 노드:3)

 

4.

 

이번에는 (거리:2, 노드:5)를 꺼낸다.

 

5번노드 또한 아직 처리되지 않았기 때문에 방문표시해주고 5번노드와 연결된 간선들을 찾아준다.

 

5번노드에서 6번노드로 가는 거리는 4(2+2) < INF 이므로 6번노드를 4로 갱신한 후 우선순위 큐에 삽입

 

5번노드에서 3번노드로 가는 거리는 3(2+1) < 4 이므로 3번노드를 3으로 갱신 후 우선순위 큐에 삽입해준다.

 

우선순위 큐

(거리:3, 노드:3) (거리:4, 노드:3) (거리:4, 노드:6) (거리:5, 노드:3)

 

5.

(거리:3, 노드:3)을 꺼낸다.

 

3과 연결된 2번노드, 6번노드의 거리를 계산해준다.

 

3번 노드의 거리는 3, 3번노드에서 2번노드로 가는 거리는 3, 합 6이므로 2번노드의 2보다 거리가 크기 때문에 갱신하지 않는다.

 

똑같이 6번 노드의 거리는 4, 3번노드(3) + 3->6(5) = 8이므로 갱신하지 않는다.

 

우선순위 큐

(거리:4, 노드:3) (거리:4, 노드:6) (거리:5, 노드:3)

 

6.

다음 최상단 튜플값은 (거리:4, 노드:3)을 꺼낸다.

 

하지만 이미 3번노드는 방문했으므로 지나간다.

 

우선순위 큐

(거리:4, 노드:6) (거리:5, 노드:3)

7.

그 다음 우선순위 큐인 (거리:4, 노드:6)을 꺼낸다.

 

근데 6번노드는 연결된 간선이 없다.

 

지나간다.

 

우선순위 큐

(거리:5, 노드:3)

 

8.

마지막 남은 우선순위 큐인 (거리:5, 노드:3)을 꺼낸다.

 

하지만 3번노드는 이미 방문 했으므로 패스

 

남아있는 큐가 없으므로 종료한다.

 

---

위의 방법으로 파이썬 표준라이브러리인 PriorityQueue와 heapq는 데이터의 개수가 N개일 때 하나의 데이터를 삽입 및 삭제할 때의 시간복잡도는 \(O(logN)\)이다.

 

# 9-2 최단 경로 개선된 다익스트라
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

# 노드의 개수, 간선의 개수 입력 받기
n, m = map(int, input().split())

# 시작 노드 번호
start = int(input())

# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
graph = [ [] for i in range(n+1) ]

# 최단 거리 테이블, 모두 무한으로 초기화
distance = [INF] * (n+1)

# 모든 간선 정보 입력받기
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append( (b, c) )
    
def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
    heapq.heappush(q, (0, start))
    distance[start] = 0
    
    while q: # 큐가 비어있지 않다면
        # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop(q) # 큐에는 (거리, 노드번호) 로 저장되어 있음
        
        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
        if distance[now] < dist:
            continue
        
        # 현재 노드와 연결된 다른 인접한 노드들 확인
        for i in graph[now]:
            cost = dist + i[1] # 그래프에는 (노드번호, 거리) 로 저장되어있음
            # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
                
# 다익스트라 알고리즘 수행
dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])

 

기존의 간단한 다익스트라 알고리즘과의 차이점이라면

 

visited 리스트가 없이 기존의 distance 리스트와 큐에서 꺼낸 값을 비교하여 방문 여부를 확인하고 있으며

 

get_smallest_node() 함수가 쓰이지 않게 되었다.