다익스트라 알고리즘(Dijkstra Algorithm)(feat.힙(heap))

 다익스트라 알고리즘

최단경로 알고리즘으로 특정 노드에서 출발해서 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.

'음의 간선'이 없을 때 정상적으로 동작하고 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다.

매번 '간선 비용'이 가장 적은 노드를 선택해서 임의의 과정을 반복하기 때문에 그리디 알고리즘을 사용하기도 하고, 다이나믹 프로그래밍(DP) 알고리즘 또한 사용한다.

사진출처 나무위키 

• 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만든다.
• 방문한 적이 있는지 체크하는 목적의 리스트를 만든다.
• 최단 거리 테이블을 하나 만들어놓고 모두 무한 (INF, 1e9 또는 987654321 로 보통 초기화시켜준다)으로 초기화 시켜준다.

파이썬 코드로 작성해보면 아래와 같이 생각할 수 있다.

def smallest_node_number():#방문하지않은 노드들 중에서 가장 최단 거리가 짧은 노드의 번호반환 함수
    min_number = INF
    node_idx = 0
    for i in range(1,n+1):
    	#distance는 노드에 연결되어 있는 노드들 까지의 거리를 넣어놓은 리스트(INF로초기화)
        #visited는 방문했으면 True로 처리 해놓는 방문했는지를 알 수 있는 리스트(False로초기화)
        if distance[i] < min_number and not visited[i]:
        #INF보다 작고(거리비교), 방문을 안했으면 min_number값을 최단거리인 노드값으로 반영
            min_number = distance[i]
            node_idx = i
    return node_idx

def dijkstra(start): #다익스트라 코드
	distance[start] = 0
    visited[start] = True
    #graph는 [[] for _ in range(n+1)] 로 만들어서 
    #for _ in range(n):
    #	a,b,c = map(int,input().split())
    #   graph[a].append((b,c))
        
    for j in graph[start]:
    	distance[j[0]] = j[1]
    for i in range(n-1:
    now = smallest_node_number()
    visited[now] = True
    for j in graph[now]:
    	cost = distance[now] + j[1]
        if cost< distance[j[0]]:
        	distance[j[0]] = cost

하지만 위와 같이 작성된 다익스트라 코드는 시간 복잡도가 O(N^2)으로 코딩테스트를 볼 때 뿐만 아니라 백준을 풀 때도 거의 시간초과에 걸린다.

그래서 아래와 같이 힙(heap)을 사용한 다익스트라를 사용해서 시간복잡도를 O(ElogN)으로 줄여서 사용하면 좋다.

우선선위 큐(PriorityQueue),힙(heap)을 사용한 다익스트라

먼저 heap에 대한 간단한 설명은 아래를 참고하면 된다.

우선순위 큐(Priority Queue)와 힙(heap)

 

파이썬에서 표준 라이브러리로 제공하는 PriorityQueue 와 heapq는 데이터 개수가 N개일 때, 하나의 데이터를 삽입, 삭제할 때 시간복잡도는 O(logN)이다. 위에 for문을 사용한 방법보다 시간이 훨씬 빠른 이유는 한 번 처리된 노드는 더이상 신경쓰지 않기 때문이다.

heapq를 사용한 다익스트라 코드는 아래와 같다.

import heapq
def dijkstra(start):
	q = []
    # 시작 노드에서 시작노드 까지의 거리는 0
    heapq.heappush(q,(0,start))
    distance[start] = 0
    while q:
    	dist, now_node = heapq.heappop(q)
        if distance[now_node] <dist:
        	continue
        for i in graph[now_node]:
        	cost = dist + i[1]
            #현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧을경우 갱신해준다.
            if cost<distance[i[0]]:
            	distance[i[0]] = cost
                heapq.heappush(q,(cost,i[0])