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

N개의 정점과 M개 간선으로 이뤄진 그래프가 있다고 하자. 이때 N개의 정점 중 하나를 시작점으로 하여 나머지 N - 1개의 정점들까지의 최단거리 경로를 구하는 알고리즘 중 하나가 다익스트라 알고리즘이다.

(참고: 간선 가중치가 없는 그래프의 최단거리 경로는 BFS를 통해 구할 수 있다.)

 

다익스트라 알고리즘은 간선에 가중치가 있는 방향 그래프에서 최단거리 경로를 구하기 위해 사용한다. 따라서 만약 방향 그래프가 아니라면 하나의 간선에 대해 양방향으로 이어지는 방향 그래프로 변환해야 한다. 즉, 무방향 그래프로 데이터가 주어지는 경우 그래프를 인접 리스트 형태로 만들어줄 필요가 있다.

 

이후 가중치의 표현은 w(A, B)라 하자. 의미는 정점 A에서 정점 B로 이동하는 가중치이다.

 

단, 가중치가 음수인 간선이 포함된 경우는 다익스트라 알고리즘으로 최단거리 경로를 구할 수 없는 것에 주의한다.

 

각 정점까지의 최단경로 즉, 최소 가중치 누계를 구해야 하므로 (key, value)가 각각 (정점, 누적 가중치)인 "최단거리 테이블"을 만들고 각 정점별 초기 가중치는 무한대(INF) 값을 지정하도록 한다.

 

다음과 같이 그래프가 주어지고 시작 정점은 1이라고 하자.

최단거리 테이블을 아래와 같이 초기화한다.

 

시작 정점은 가중치가 0인 상태로 시작하므로 정점 1의 값을 0으로 변경한다.

 

시작 정점으로부터 뻗어나가는 간선들이 있을 때,  간선들을 통해 도착하는 정점에 해당하는 최단거리 테이블 값을 이동에 사용된 간선의 가중치로 변경한다.

 

 

최단거리 테이블의 값이 변경되는 경우 (도착 정점의 누적 가중치, 도착 정점) 형태로 우선순위 큐(min heap)에 넣는다. (이 과정은 이후로도 동일하다.)

 

이제 우선순위 큐가 비워질 때까지 다음 작업을 반복한다.

우선순위 큐의 데이터를 하나 pop 하고 이를 current node라 하자. (current node는 현재 시점에서 누적 가중치가 가장 낮은 정점이다.)

current node로부터 뻗어나가는 모든 간선에 대해 다음과 같이 처리한다.

• 최단거리 테이블[current node] < current node [0]인 경우 즉, current node의 최단거리가 업데이트되기 전에 우선순위 큐에 추가된 최단거리의 경우 우선순위 큐의 데이터는 쓰레기 데이터이므로 아무것도 하지 않는다.
• current node와 연결된 도착 정점의 누적 가중치 >  current node의 누적 가중치 + w(current node, 도착 정점) 인지 확인한다.
  • 조건을 만족하면 최단거리 테이블에서 도착 정점의 누적 가중치를 current node의 누적 가중치 + w(current node, 도착 정점)으로 업데이트하고 우선순위 큐에 (도착 정점의 누적 가중치, 도착 정점)을 insert 한다.
  • 조건을 만족하지 않는다면 아무것도 하지 않는다.

 

 

위에 그림에 해당하는 그래프에 대한 입력으로

첫째 줄에 정점의 수 N과 간선의 수 M이 주어지고

다음 M행에 걸쳐 정점 1, 정점 2, 가중치 형태로 간선 정보가 주어지고

마지막 줄에 시작 정점이 주어지는 경우

6 7
1 2 2
2 3 3
2 6 1
3 4 5
3 5 1
3 6 6
4 5 2
1

 

시작 노드로부터 모든 노드로의 최단거리를 아래와 같이 출력하는 코드를 작성해본다.

0 2 5 8 6 3

 

다익스트라 알고리즘

import heapq


def dijkstra():
    INF = int(1e9)
    dist = [INF] * (N + 1)
    dist[start] = 0
    heap = list()
    heapq.heappush(heap, (dist[start], start))
    #for next_node, weight in graph[start]:
    #    dist[next_node] = weight
    #    heapq.heappush(heap, (weight, next_node))
    while heap:
        acc_weight, curr_node = heapq.heappop(heap)
        if dist[curr_node] < acc_weight:
            continue
        for next_node, weight in graph[curr_node]:
            if dist[next_node] > acc_weight + weight:
                dist[next_node] = acc_weight + weight
                heapq.heappush(heap, (dist[next_node], next_node))

    return dist


N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
for _ in range(M):
    N1, N2, W = map(int, input().split())
    graph[N1].append([N2, W])
    graph[N2].append([N1, W])
start = int(input())
res = dijkstra()
print(' '.join(map(str, res[1:])))

 

---

이하는 이전에 작성한 글로 다시 읽어 봤을 때 설명이 어려워 몇 가지 그림과 함께 새롭게 작성함. 필요한 경우에 한해 이하의 내용을 참고.

 

기본적인 아이디어는 현재 노드에서 다음 노드까지 갈 수 있는 최소한의 비용을 선택하는 것이다. 예를 들어 노드 1에서 노드 2로 이동할 때  기존 비용과 새롭게 산출된 비용이 다음과 같다고 하자.

 

    기존 비용 A = 현재 노드 2까지의 최소 비용

    새로운 비용 B = 노드 1까지의 최소비용 + 노드 1 -> 노드 2 간의 간선 가중치

 

만약 A > B 이면 노드 2까지의 최소비용은 B로 변경된다.

이것은 가장 좋은 것만 선택하는 탐욕 법과 그 맥락이 같다.

 

다익스트라 알고리즘의 동작 순서를 정리하면 다음과 같다.

1. 최단거리 테이블(시작 노드로부터 현재 인덱스에 해당하는 노드의 최단거리를 저장하는 리스트)의 모든 값을 무한대(int(1e9))로 초기화한다.
2. 시작 노드를 방문 중인 노드로 설정하고, 시작 노드에 해당하는 최단거리 테이블의 값을 0으로 초기화한다.
3. 방문 중인 노드로부터 이동할 수 있는 노드들의 값을 다음과 같이 업데이트한다.
   • 방문 중인 노드에 해당하는 최단거리 테이블의 값을 ①라 한다.
   • 이동 가능한 노드로 이어지는 간선의 가중치를 ②라 한다.
   • 이동 가능한 노드에 해당하는 최단거리 테이블의 값을 ③이라 한다.
   • ① + ② < ③ 을 만족할 때 ③을 ① + ② 로 업데이트한다. 
   • 현재 노드에서 이어진 다음 노드가 있을 때, 다음 노드에 저장된 누적 가중치 < 현재 노드의 가중치 + 이어진 간선 가중치 이면 이미 더 짧은 경로가 존재한다는 뜻이므로 최단거리 테이블을 업데이트하지 않는다. 반대의 경우에는 현재 노드에서 다음 노드로 가는 것이 현시점에서의 최단 경로가 되므로 최단거리 테이블을 현재 노드 가중치 + 다음 노드로의 연결 간선 가중치로 업데이트해준다.
4. 아직 방문하지 않은 노드들 가운데  최단 거리가 가장 짤은 노드를 방문 중인 노드로 설정한다.
5. 방문하지 않은 노드가 하나밖에 없을 때까지 3, 4를 반복한다.

 

 

다익스트라 알고리즘의 구현

import sys

fast_input = sys.stdin.readline
INF = int(1e9)
# node_count = 노드 개수, edge_count = 엣지 개수
node_count, edge_count = map(int, fast_input().split())
# 시작 노드 설정
start_node = int(fast_input())
# edge의 방향성과 가중치를 지정하여 graph를 구성.
graph = [[] for _ in range(node_count + 1)]
for _ in range(edge_count):
    index_from, index_to, weight = map(int, fast_input().split())
    graph[index_from].append([index_to, weight])
# 최단거리 테이블 작성
minimum_cost_table = [INF] * (node_count + 1)
# 방문 history용 리스트
visited = [False] * (node_count + 1)


# 현재 노드에 연결된 노드 중 코스트가 가장 낮은 노드를 찾는다.
def get_minimum_cost_node():
    min_value = INF
    min_index = 0
    for index in range(1, node_count + 1):
        if not visited[index] and minimum_cost_table[index] < min_value:
            min_value = minimum_cost_table[index]
            min_index = index
    return min_index


# dijkstra algorithm
def dijkstra(s_node):
    # 시작 노드 초기화
    minimum_cost_table[s_node] = 0
    visited[s_node] = True
    for next_node_n_weight in graph[s_node]:
        minimum_cost_table[next_node_n_weight[0]] = next_node_n_weight[1]
    # 시작 노드를 제외한 나머지 노드들에 대해 다음을 반복
    # 1. 가장 코스트가 낮은 노드를 선택하고 방문처리
    # 2. 방문 처리한 노드와 연결된 다른 노드를 확인하면서 "현재 노드 가중치 + 간선 가중치 < 연결된 노드 가중치" 인 경우
    #    최소 비용 테이블의 값을 "현재 노드 가중치 + 간선 가중치"로 업데이트 한다.
    for _ in range(node_count - 1):
        current_node = get_minimum_cost_node()
        visited[current_node] = True
        for next_node_n_weight in graph[current_node]:
            if minimum_cost_table[current_node] + next_node_n_weight[1] < minimum_cost_table[next_node_n_weight[0]]:
                minimum_cost_table[next_node_n_weight[0]] = minimum_cost_table[current_node] + next_node_n_weight[1]


dijkstra(start_node)

for i in range(1, node_count + 1):
    if minimum_cost_table[i] == INF:
        print("Infinity")
    else:
        print(minimum_cost_table[i])

이 알고리즘의 시간 복잡도는 방문하지 않은 모든 노드 가운데 노드까지의 이동거리가 가장 짧은 노드를 노드 개수만큼 선형 탐색해야 하고  그 결과로 결정된 최단 거리 노드를 기준으로 연결된 노드를 확인해야 하므로 O(V^2)이 (V는 노드 수) 된다.

 

 

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

아직 방문하지 않은 최저 비용 노드를 탐색할 때 선형 탐색 대신 heap 자료구조를 활용한 탐색을 통해 다익스트라 알고리즘의 시간 복잡도를 개선할 수 있다.

import heapq
import sys

fast_input = sys.stdin.readline
INF = int(1e9)
node_count = int(input('How may nodes: '))
edge_count = int(input('How many edges: '))
start_node = int(input('Set the start node: '))
# lowest_cost_table declaring and initializing
lowest_cost_table = [INF] * (node_count + 1)
# graph setting
graph = [[] for _ in range(node_count + 1)]
print('Set edge info. (e.g) from node, to node, weight -> 1 2 2')
for i in range(edge_count):
    print(f'edge info ({i + 1}/{edge_count}):', end='', flush=True)
    from_node, to_node, edge_cost = map(int, fast_input().rstrip().split())
    graph[from_node].append([to_node, edge_cost])


# dijkstra algorithm
def dijkstra(s_node):
    # visited_nodes = list()
    lowest_cost_table[s_node] = 0
    priority_queue = list()
    heapq.heappush(priority_queue, (0, s_node))  # the tuple's values consist of cost and node
    while priority_queue:
        current_cost, current_node = heapq.heappop(priority_queue)
        # if from_node in visited_nodes:
        if lowest_cost_table[current_node] < current_cost:
            continue
        # visited_nodes.append(from_node)
        for next_node, edge_weight in graph[current_node]:
            if lowest_cost_table[next_node] > current_cost + edge_weight:
                lowest_cost_table[next_node] = current_cost + edge_weight
                heapq.heappush(priority_queue, (lowest_cost_table[next_node], next_node))


dijkstra(start_node)
for i in range(1, len(lowest_cost_table)):
    # cost = lowest_cost_table[i] == INF ? "Infinity":lowest_cost_table[i]
    cost = "Infinity" if lowest_cost_table[i] == INF else lowest_cost_table[i]
    print(f'lowest cost to {i} node is {cost}')

 

위의 개선된 다익스트라 알고리즘에 대한 입력 값이 다음과 같이 주어지면

다익스트라 알고리즘 입력 예시

다음과 같이 출력된다.

상기 입력 밧에 따른 결과 출력

 

 

그래프 정보가"노드 A  노드 B  가중치" 형태로 주어지는 경우는 다음의 make_graph 함수를 사용해 상기 알고리즘에 요구하는 인접 리스트 형태의 그래프 정보로 변환하자.

def make_graph(N, input_datas):
    '''
    :param N: node count
    :param input_data: 2D list of connection between node nad node
    :return: graph information that is adjacency list type
    '''
    graph = [[] for _ in range(N + 1)]
    for input_data in input_datas:
        graph[input_data[0]].append([input_data[1], input_data[2]])
        graph[input_data[1]].append([input_data[0], input_data[2]])
    return graph

N = 5
E = 5
# 1 2 1
# 1 4 2
# 2 3 3
# 3 4 1
# 4 5 2
data = list()
for _ in range(E):
    data.append(list(map(int, input().split())))

# edge count만큼 data를 입력
graph = make_graph(5, data)
print(graph)