[알고리즘] 다익스트라(Dijkstra) 알고리즘

1. 다익스트라(Dijkstra) 알고리즘이란

• 음의 가중치가 없는 그래프의 한 정점에서 다른 정점까지의 최단 경로(거리)를 구하는 알고리즘이다.
• 음의 가중치가 있을 때는 벨만-포드 알고리즘을 사용할 수 있다.
• 가능한 모든 노드쌍의 최단 거리를 구할 때는 플로이드-워셜 알고리즘을 사용한다.
• BFS를 기본으로 한다.

 

2. 다익스트라 알고리즘 동작 방식

1. 출발 노드로부터 각 노드까지 최단 경로를 저장할 배열 distance[v]를 초기화하고, 출발 노드의 인덱스에는 0, 다른 노드에는 매우 큰 값을 저장한다(무한에 근접하도록 distance의 원소 타입의 최댓값으로 설정하면 된다).
2. 현재 노드를 뜻하는 노드 A에 출발 노드 번호를 저장한다.
3. A로부터 갈 수 있는 임의의 노드 B에 대해, A까지 최단거리(distance[A]) + A에서 B까지의 거리(graph[A][B])와 기존에 계산한 B까지의 최단거리(distance[B])를 비교한다. (min(distance[A]+graph[A][B], distance[B])) INF와 비교할 경우 무조건 전자가 작다.
4. 만약 전자가 더 작다면, 즉 더 짧은 경로일 경우 distance[B]를 갱신한다.
5. A의 모든 인접 노드에 대해 이 작업을 수행한다.
6. 모든 인접 노드에 대해 위 작업을 마쳤으면, A를 '방문 완료'로 처리하여 중복 탐색을 방지한다.
7. '미방문' 상태인 모든 노드들 중, 출발점으로부터 거리가 가장 짧은 노드를 하나 골라서 그 노드를 A에 저장한다.
8. 도착 노드가 '방문 완료' 상태가 되거나, 혹은 더 이상 미방문 상태의 노드를 선택할 수 없을 때까지, 3~7을 반복한다.

이 작업을 마친 뒤, 도착 노드에 저장된 값(distance[end])이 바로 A로부터의 최단 거리이다. 만약 이 값이 INF라면, 중간에 길이 끊긴 것임을 의미한다.

 

 

3. 구현(파이썬)

3.1 단순한 방식

def dijkstra(start, n):
    infos = [[1, 2, 2], [1, 3, 1], [2, 4, 1], [2, 5, 2], [3, 4, 3], [4, 5, 1], [5, 6, 1]]
    INF = 10e9
    distance = [INF] * (n + 1)
    graph = [[] for i in range(n + 1)]
    visited = [False] * (n + 1)  
	
    for v, w, u in infos:
        graph[v].append((w, u))
        
    for v, w in graph[start]:
        distance[v] = w

    def get_smallest_node():
        smallest_value = INF
		index = 1
        for i in range(1, n+1):
            if distance[i] < smallest_value and not visited[i]:
                smallest_value = distance[i]
                index = 0
        return index
        
        
    for _ in range(n-1):
        now = get_smallest_node()
        visited[now] = True
        for child in graph[now]:
            c_node = child[0]
            cost = distance[now] + child[1]
            if cost < distance[c_node]:
                distance[c_node] = cost

이 경우 시간복잡도는 \(O(v^2)\)이다.

 

 3.2 우선순위큐 이용

from collections import defaultdict
import heapq

infos = [[1, 2, 2], [1, 3, 1], [2, 4, 1], [2, 5, 2], [3, 4, 3], [4, 5, 1], [5, 6, 1]]
INF = 10e9
distance = defaultdict(int)
graph = defaultdict(list)

Q = []

for u, v, w in infos:
    graph[u].append([v, w])
 
Q.append((0, start))

while Q:
    current_cost, current_node = heapq.heappop(Q)
    if  distance[current_node] < current_cost:
        continue
    for child in graph[current_node]:
        child_node = child[0]
        child_cost = child[1]
        alt_cost = current_cost + child_cost
        if alt_cost < distance[child_node]:
            heapq.heappush(Q, (alt_cost, child_node))

print(distance)

 

※ 우선순위 큐를 활용한 다익스트라 알고리즘의 시간복잡도

우선순위 큐를 사용할 경우 위 동작방식 7번에서 시간복잡도를 크게 줄일 수 있다.

우선순위 큐를 사용하면 한번 처리된 노드는 더이상 처리되지 않는다. 즉 노드를 하나씩 꺼내 검사하는 반복문(while문)은 노드의 개수 V 이상의 횟수로는 반복되지 않는다. 또한 V번 반복될 때마다 각각 자신과 연결된 간선들을 모두 확인한다. 따라서 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총 횟수는 총 최대 간선의 개수 E만큼 연산이 수행될 수 있다. 일반적으로 힙연산의 시간복잡도는 \(O(logn)\)이고 \(O(logE)\)를 E개의 원소에 대하여 반복하는 것으로 볼 수 있으므로 시간복잡도는 \(O(ElogE)\)로 표현할 수 있다. 

이때 중복 간선을 포함하지 않는 경우, E는 항상 V의 제곱보다 작다. 왜나하면, 모든 노드끼리 서로 다 연결되어 있다고 했을 때 간선의 개수를 약 \(V^2\)으로 볼 수 있고 항상 E는 \(V^2\)이하이기 때문이다.

\(O(ElogE)\) <= \(O(ElogV^2)\)이고, \(O(ElogV^2)\)는 \(O(2*ElogV)\)이므로 \(O(ElogV)\)로 표현할 수 있다.