[파이썬으로 배우는 알고리즘] 다익스트라(Dijkstra) 알고리즘

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

다익스트라(Dijkstra) 알고리즘은 최단 경로 알고리즘으로 그래프에서 특정한 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘입니다. 그리디 알고리즘 기반에 동적 계획법을 활용한 알고리즘이며 그래프에서 양수 가중치만 있을 때 사용할 수 있습니다. 그러면 과정을 그림과 함께 보면서 다익스트라 알고리즘이 어떻게 동작하는지 알아보도록 할게요!

2022.07.04 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 그래프(Graph)

[파이썬으로 배우는 자료구조] 그래프(Graph)

2022.07.18 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 그리디(Greedy) 알고리즘

[파이썬으로 배우는 알고리즘] 그리디(Greedy) 알고리즘

2022.07.22 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming)

[파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming)

 

---

다익스트라 알고리즘의 동작

동작 설명

1) 거리, 방문 테이블 준비(거리 테이블은 INF, 방문 테이블은 False로 모두 초기화)

2) 시작 노드 선택(방문 처리)

3) 연결되어 있는 노드와의 최단 거리를 구함(거리 테이블 갱신)

4) 갱신 후 아직 방문하지 않은 노드 중 가장 거리가 짧은 노드를 선택(방문 처리)

5) 3~4번 반복

 

동작 예시

1) 거리 테이블의 값은 해당 노드로 연결되어 있지 않다는 것을 의미(해당 노드로 갈 수 없음을 의미하는 값)하는 INF값으로 모두 설정하고, 방문 테이블의 값은 해당 노드를 아직 방문하지 않았음을 의미하는 False로 모두 설정합니다.

 

2) 시작 노드를 1로 선택하여 방문 처리하고 시작 노드의 거리는 0이므로 거리 값을 0으로 설정합니다.

 

3) 노드 1과 연결된 노드와의 간선의 가중치에 따라 각 노드와의 거리를 갱신합니다. INF보다 각 가중치의 값이 작으므로 전부 갱신을 해줍니다.

 

4) 방문하지 않은 노드 중 거리 값이 가장 작은 노드 6을 선택해 방문합니다.

 

5) 6과 연결된 노드와의 간선의 가중치에 따라 각 노드와의 거리를 업데이트합니다. 6번 노드는 1번 노드와의 거리가 2이고 3, 5번 노드는 각각 6번 노드와의 거리가 5, 3이므로 1번 노드와의 거리를 더한 값으로 업데이트해줍니다. (6번 노드를 경유해서 갈 수 있음을 의미)

 

6) 방문하지 않은 노드 중 거리 값이 가장 작은 노드 2를 선택해 방문합니다.

 

7) 원래 3번 노드와 1번 노드의 거리는 7이었지만 1번 노드와 2번 노드의 거리 3과, 2번 노드와 연결된 3번 노드의 거리 1의 합이 4로 7보다 작으므로 4로 갱신해줍니다.

 

마찬가지로 4번 노드도 1번 노드와의 거리가 8이었지만 1번 노드와 2번 노드의 거리 3과, 2번 노드와 연결된 4번 노드의 거리 4의 합이 7로 8보다 작으므로 7로 갱신해줍니다.

 

8) 방문하지 않은 노드 중 거리 값이 가장 작은 노드 3을 선택해 방문합니다.

 

9) 노드 1에서 노드 3을 경유하여 노드 6으로 갈 경우 4 + 5의 값이 원래의 값 2보다 작으므로 갱신하지 못하고, 노드 5로 갈 경우 4 + 1의 값은 원래의 값 5와 같으므로 갱신하지 못합니다. 따라서 테이블에는 어떤 변화도 없습니다.

 

10) 방문하지 않은 노드 중 거리 값이 가장 작은 노드 5를 선택해 방문합니다.

 

11) 마찬가지로 갱신할 수 없습니다.

 

12) 방문하지 않은 노드 중 거리 값이 가장 작은 노드 4를 선택해 방문합니다.

 

13) 1을 시작 노드로 다른 노드와의 최단 거리를 모두 구했습니다.

 

왜 그리디 기반? 계속해서 가장 거리 값이 작은 노드만 선택하기 때문이죠!(최적 부분 구조, 탐욕적 선택 속성)

왜 동적 계획법? 최단 거리는 여러 개의 최단 거리로 구성되어 있어요! 이전까지의 최단 경로들이 최단 경로를 구하기 위해 재사용돼요!(최적 부분 구조, 겹치는 부분 문제)

 

---

다익스트라 알고리즘 구현

순차 탐색

코드

# 방문하지 않은 노드 중 거리가 가장 작은 노드를 찾음
def get_min_node():
    min_dis = INF
    node = 0
    
    for i in range(1, NODE_CNT + 1):
        if dis[i] < min_dis and not visited[i]:
            min_dis = dis[i]
            node = i
            
    return node

# 다익스트라
def dijkstra(start):
    dis[start] = 0
    visited[start] = True
    
    for i in range(1, NODE_CNT + 1):
        if graph[start][i] != 0:
            dis[i] = graph[start][i]
    
    for i in range(NODE_CNT-1):
        min_node = get_min_node()
        visited[min_node] = True
        
        for j in range(1, NODE_CNT + 1):
            # min_node를 경유하여 가는 거리가 더 짧으면 갱신
            if graph[min_node][j] != 0 and dis[min_node] + graph[min_node][j] < dis[j]:
                dis[j] = dis[min_node] + graph[min_node][j]
              
    print(dis[1:])
    print(visited[1:])  

    
if __name__ == "__main__":
    NODE_CNT = 6
    INF = 2147000000
    graph = [[0] * (NODE_CNT + 1) for _ in range(NODE_CNT + 1)]
    graph[1][2], graph[1][4], graph[1][6] = 3, 8, 2
    graph[2][1], graph[2][3], graph[2][4] = 3, 1, 4
    graph[3][2], graph[3][5], graph[3][6] = 1, 1, 5
    graph[4][1], graph[4][2] = 8, 4
    graph[5][3], graph[5][6] = 1, 3
    graph[6][1], graph[6][3], graph[6][5] = 2, 5, 3
    
    dis = [INF] * (NODE_CNT + 1)
    visited = [False] * (NODE_CNT + 1)
    
    dijkstra(1)

결과

시간 복잡도

위의 코드는 순차 탐색을 사용해 최단 거리를 찾는 방식으로 노드의 개수만큼 순차 탐색이 수행됩니다. 각 노드마다 순차 탐색으로 노드와의 거리를 구해 갱신해야 하는 작업을 해야 하므로 O(N^2)의 시간 복잡도를 갖게 되어 비효율적으로 동작하게 됩니다. 그렇다면 이를 보완할 수 있는 방법은 없을까요?

 

 

우선순위 큐

바로 우선순위 큐를 사용하여 최단 거리를 찾는 방식이 있습니다. 순차 탐색으로 최단 거리를 하나하나 찾는 것이 아니라 노드에 방문 후 연결된 노드에 대한 간선 정보를 우선순위 큐(최소힙)에 넣어 최단 거리를 찾는 과정에서는 pop만 하여 최단 거리를 찾을 수 있으므로 보다 더 효율적으로 동작하게 됩니다.

 

2022.07.19 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 우선순위 큐(Priority Queue), 힙(Heap)

[파이썬으로 배우는 자료구조] 우선순위 큐(Priority Queue), 힙(Heap)

 

코드

import heapq as hq

# 다익스트라 알고리즘
def dijkstra(start):
    dis[start] = 0
    # 시작 노드 삽입
    hq.heappush(heap, (0, start))
    
    # 힙에 데이터가 존재할때 까지
    while heap:
        w, v = hq.heappop(heap)
        # 이미 최단 거리가 가중치보다 작으면 생략
        if dis[v] < w:
            continue
        
        for next_v, added_w in graph[v]:
            # 경유
            next_w = w + added_w
            # 경유해서 가는 거리가 더 짧으면 갱신
            if next_w < dis[next_v]:
                dis[next_v] = next_w
                hq.heappush(heap, (next_w, next_v))
    print(dis[1:])

if __name__ == "__main__":
    NODE_CNT = 6
    INF = 2147000000
    graph = [[] for _ in range(NODE_CNT+1)]
    dis = [INF] * (NODE_CNT+1)
    heap = list()
    
    graph[1].append((2, 3))
    graph[1].append((4, 8))
    graph[1].append((6, 2))
    graph[2].append((1, 3))
    graph[2].append((3, 1))
    graph[2].append((4, 4))
    graph[3].append((2, 1))
    graph[3].append((6, 5))
    graph[3].append((5, 1))
    graph[4].append((1, 8))
    graph[4].append((2, 4))
    graph[5].append((3, 1))
    graph[5].append((6, 3))
    graph[6].append((1, 2))
    graph[6].append((3, 5))
    graph[6].append((5, 3))
    
    dijkstra(1)

결과

시간 복잡도

간선의 개수를 E 노드의 개수를 N이라 할 때 우선순위 큐에서 꺼낸 노드와 연결된 노드들만 탐색하므로 최악의 경우에도 E만큼 반복을 합니다. 우선순위 큐에 E개의 간선을 넣었다가 빼는 것으로 시간 복잡도가 O(E log E)가 되는데 E는 항상 N^2보다 작으므로 log E는 log N^2보다 작게 되고 이는 하나의 간선에 대해 걸리는 시간 복잡도가 O(log N)라고 볼 수 있습니다. 따라서 시간 복잡도는 총 O(E log N)이 되어 순차 탐색으로 구현한 것보다 더 효율적인 다익스트라 알고리즘을 구현할 수 있습니다.