🧿 Dijkstra's (Shortest Path) Algorithm

intro

🧿 다익스트라 알고리즘이란 '방향 그래프 또는 무방향 그래프에서 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘'이다. 플로이드 알고리즘은 모든 정점 쌍 사이의 최단 거리를 일일이 구하는 알고리즘. 플로이드 알고리즘은 음수인 간선 존재는 괜찮지만 음수인 사이클이 있을 때만 문제이나, 다익스트라는 음수인 가중치를 가지는 간선이 있으면 아예 사용 불가능. 음수인 간선이 있다면 벨만포드 알고리즘 사용. 또한 정확한 최단거리가 아닌 근사치를 원할 경우 A* 알고리즘을 사용함. 다익스트라는 네트워크에서도 많이 사용.

 

🧿 일명 '최단 경로 알고리즘' 중 하나로, 최단 경로 문제 상황은 (1) 한 지점에서 다른 한 지점까지의 최단 경로 (2) 한 지점에서 다른 모든 지점까지의 최단 경로 (3) 모든 지점에서 다른 모든 지점까지의 최단경로 이렇게 3가지로 나눌 수 있다. 다익스트라는 (2)이며, 그리디 알고리즘으로 분류 → 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다. 또한, A →  C까지 가는 최단경로 알고리즘은 일반적으로  A → B로 간 케이스에서 B → C 까지 이동하는 경우를 고려하는, 기본적으로 DP의 원리가 들어간 알고리즘. 다익스트라는 음수인 간선이 없을 경우 동작하는 알고리즘이기 때문에 실제 현실 세계에서 도로(간선)가 음의 간선으로 표현되지 않는 점으로 미루어 보아 현실세계에 적용 가능한 알고리즘이다.

 

🧿 알고리즘 동작 과정

① 출발 노드 설정

 

② 최단 거리 테이블 초기화: 처음에 모든 노드까지 가기 위한 비용 무한대 설정, 자기 자신(출발 노드)은 0으로 설정

 

③ <그리디> 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드 선택
(이 때, 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않는다. 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해)

 

④ <dp> (위 선택한 최단 거리가 가장 짧은) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신

 

⑤ 위 과정에서 ③과 ④과정을 반복. 이후 모두 수행하면 테이블에 출발 노드에서 각 노드까지의 최단 거리 정보가 저장된다.

implementation

① without using Priority Queue

🧿 구체 과정

① 그래프 준비 / 출발 노드 설정 / 최단 거리 테이블 설정

② 방문하지 않은 노드 중에 최단 거리가 가장 짧은 노드인 1번 노드(거리 0) 방문 처리 + 노드 1에서 인접한 노드들 중 거리 업데이트(노드 2와 노드 3과 노드4): 기존 테이블 값과 노드1까지의 최단거리와 간선 거리 합 두 개를 비교해서 최솟값으로 업데이트

③ 방문하지 않은 노드 중 최단거리가 가장 짧은 노드 3번 선택 → 3번 노드 방문 처리 + 인접 노드 4번 노드 거리 업데이트(현재 3번 노드 최단거리 2 + 간선 2의 합 4가 5보다 작으므로 4로 업데이트)

 

④ 방문하지 않은 노드 중 최단거리가 가장 짧은 노드 2번 선택 → 2번 노드 방문 처리 + 인접노드 5번 노드 거리 업데이트(현재 2번 노드 최단거리 3 + 간선 8의 합 11이 inf보다 작으므로 11로 업데이트)

⑤ 방문하지 않은 노드 중 최단거리가 가장 짧은 노드 4번 선택 → 4번 노드 방문 처리 + 인접노드 5번 노드 거리 업데이트(현재 4번 노드 최단거리 4 + 간선 6의 합 10이 11보다 작으므로 10으로 업데이트)  

 

⑥ 방문하지 않은 노드 중 최단거리가 가장 짧은 노드 5번 선택 → 5번 노드 방문 처리 + 인접노드 6번 노드 거리 업데이트(현재 5번 노드 최단거리 10 + 간선 1의 합 11이 inf보다 작으므로 11로 업데이트) 

 

⑦ 방문하지 않은 노드 중 최단거리가 가장 짧은 노드 6번 선택 → 6번 노드 방문 처리 + 인접노드 6번 노드가 없고 방문 안한 노드가 없으므로 종료

 

🧿 python code

import sys
input=sys.stdin.readline
INF = int(1e9)

n,m=map(int,input().split()) #node number, line number
start=int(input()) #start node
graph=[[]for i in range(n+1)] #graph list
visited=[False]*(n+1)
distance=[-1]+[INF]*(n) #shortest-path distance arr

#forms graph
for _ in range(m):
    a,b,c=map(int,input().split())
    graph[a].append((b,c)) #node a -> node b (cost c)

#returns the smallest paths of node among non-visited
def get_smallest_node():
    min_value=INF
    index=0 #the smallest node's index
    for i in range(1,n+1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i
    return index

def dijkstra(start):
    distance[start] = 0 #initialize 0 in start node in sp distance arr
    visited[start] = True
    for j in graph[start]:
        distance[j[0]] = j[1] #update sp arr starting from start node
    
    for _ in range(n-1): #n-1 times (start node operated above)
        now = get_smallest_node()
        visited[now] = True
        for j in graph[now]: #update sp arr starting from each node
            cost = distance[now] + j[1]
            if cost < distance[j[0]]:
                distance[j[0]] = cost

dijkstra(start)

print(distance) #print sp arr table

 

🧿 문제점: 매 번 최단 거리가 가장 짧은 노드를 선형탐색해야 한다(위 get_smallest_node() 함수). 따라서 위 코드는 table update를 위한 모든 노드 탐색 + 매 탐색 시 탐색 시작 노드를 정하기 위한 get_smallest_node() 이렇게 O(V*V)의 시간 복잡도가 걸린다. (V는 간선의 개수). 일반적으로 전체 노드의 개수가 5,000개 이하라면 위 코드로 문제 해결 가능. 하지만 노드의 개수가 10,000개를 넘어간다면 TLE.

② using Priority Queue

🧿 따라서 이 문제를 해결하기 위해 더 효율적인 다익스트라 알고리즘을 구현을 위해서는 우선순위 큐(Priority Queue) 자료구조 사용(포스팅 참조). 우선순위 큐란 '우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조'. 예를 들어 여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인해야 하는 경우 우선순위 큐 사용. 우선순위 큐에는 최소 힙(min heap)과 최대 힙(max heap) 존재. 최소 힙은 값이 낮은 데이터부터 먼저 삭제. 최대 힙은 값이 높은 데이터부터 먼저 삭제. 데이터 삽입과 삭제에 모두 O(logn).

 

🧿 다익스트라 알고리즘에서 '방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택하는 과정' get_smallest_node()의 알고리즘 시간복잡도를 우선순위 큐로 개선할 수 있다. 현재 최단거리가 가장 짧은 노드를 선택해야 하므로 최소 힙 사용. 

 

① 그래프 준비 / 출발 노드 설정 / 최단거리 테이블 설정 / 우선순위 큐에 출발 노드 삽입

② 우선순위 큐에서 원소 꺼냄. 1번 노드는 아직 방문하지 않았으므로 방문 처리. 1번 노드와 연결된 2번 노드 / 3번 노드 / 4번 노드 최단 거리 update. 세 개 노드 모두 최단 거리가 업데이트 되었으므로 우선순위 큐에 삽입. 

 

③ 우선순위 큐에서 원소 꺼냄. 3번 노드는 방문하지 않았으므로 방문 처리. 3번 노드와 연결된 4번 노드 최단 거리 업데이트. 4번 노드 최단 거리가 업데이트 되었으므로 우선순위 큐에 삽입. 

 

④ 계속해서 우선순위 큐에서 원소 꺼냄. 2번 노드 역시 방문하지 않았으므로 방문 처리하고 연결 노드 5번의 최단 거리 업데이트 뒤, 우선순위 큐에 5번 노드를 업데이트한 최단거리와 함께 삽입.

 

⑤ 계속해서 우선순위 큐에서 거리가 4인 노드 4를 꺼내고 방문 처리한 뒤, 연결 노드 5번의 최단거리를 10으로 업데이트 하고 우선순위 큐에 삽입.

 

⑥ 우선순위 큐에서 거리가 5인 노드 4를 꺼냈으나, 노드 4는 이미 방문처리했으므로 패스. 거리가 10인 노드 5를 꺼내고 방문 처리한 뒤, 연결 노드 6번의 최단거리를 11로 업데이트 하고 우선순위 큐에 삽입.

 

⑦ 우선순위 큐에서 거리가 11인 노드 5를 꺼냈으나 노드 5는 이미 방문처리했으므로 패스. 거리가 11인 노드 6을 꺼내고 방문 처리한 뒤, 노드 6에 연결된 노드 없으므로 패스. 우선순위 큐에 대기 중인 노드 없으므로 종료. 

 

🧿 python code

 

※ 주의: 우선순위 큐에서 꺼낸 (거리, 노드) 쌍을 실제 최단 거리 테이블의 값과 비교할 떄 방문 처리 여부 검사를 최단 거리 테이블의 값과 같은 지 / 다른 지의 여부로 검사 (따로 visited list 만들 필요 x)

 

※ 주의: 단방향인지 / 양방향인지 구분. 양방향이라면 graph[a]와 graph[b] 각각 apppend 필요

import sys
import heapq
input=sys.stdin.readline
INF = int(1e9)

n,m=map(int,input().split()) #node number, line number
start=int(input()) #start node
graph=[[]for _ in range(n+1)] #graph list
distance=[-1]+[INF]*(n) #shortest-path distance arr

#forms graph
for _ in range(m):
    a,b,c=map(int,input().split())
    graph[a].append((b,c)) #node a -> node b (cost c)

def dijkstra(start):
    q = [] #priority-queue
    heapq.heappush(q, (0, start)) #(shortest distance, node number)
    distance[start] = 0 #initialize 0 in start node in sp distance arr

    while q:
        cur_dist, cur_node = heapq.heappop(q) #get the shortest dist with node
        if cur_dist <= dist_table[cur_node]: #if not visited
            for next_node in graph[cur_node]: #BFS
                next_node_number, next_node_dist = next_node[0], next_node[1]
                cost = cur_dist + next_node_dist #get cost(current + next dist)
                if cost < distance[next_node_number]: #if should it be updated
                    distance[next_node_number] = cost #update
                    heapq.heappush(q,(cost,next_node_number)) #insert in PQ

dijkstra(start)

print(*distance[1:]) #print sp arr table(from node 1)

 

🧿 우선순위 큐 관점으로 보았을 때 간선 1개당 최대 1개의 원소가 우선순위 큐에 추가될 수 있기 때문에 시간 복잡도는 O(ElogE). 앞서 우선순위 큐 사용이 없는 시간 복잡도는 O(V^2)로, E가 V^2에 가깝다면 시간 복잡도가 비슷해, 우선순위 큐 사용의 효과가 없으나 다익스트라 문제에서는 V를 크게 두고(즉, 노드의 개수를 크게 두고), E는 V^2까지 안가게끔 (간선의 개수는 작게) 하는 경우가 많아서 상관 x

③ Dijkstra path 경로 출력하기

---

BaaaarkingDog

이코테