[ 알고리즘 개념 ] 다익스트라 알고리즘 (Dijkstra Algorithm) 구현 - 파이썬(Python)

다익스트라 알고리즘 (Dijkstra Algorithm) 구현 - 파이썬(Python)

 

 

다익스트라 알고리즘에 대한 개념은 이전 게시글에 정리해두었다.

codingexplore.tistory.com/51?category=886802

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

이번에는 파이썬 (Python) 으로 어떻게 다익스트라 알고리즘을 구현할 것인가에 대한 것이다.

 

구현 1 : 간단한 다익스트라 알고리즘 - O(V^2)

 

첫번째 구현방법은 구현하기에는 간단하지만 O(V^2) 의 높은 시간복잡도를 가진다. ( V : 노드의 개수 ) 

 

1) 각 노드의 최단거리를 담은 1차원 리스트 선언

2) 방문하지 않은 최단거리 노드를 선택하기 위하여 매 단계마다 리스트를 순차탐색한다.

 

여기서 모든 리스트를 순차탐색한다는 점이 시간복잡도를 높이는 원인이다.

직관적으로 이해하기 쉽기 때문에 이해만 하고 넘어가도 좋다.

 

 

# 간단한 다익스트라 알고리즘 코드 (O(V^2))
import sys
input = sys.stdin.readline
INF = int(1e9) # 임의로 무한값을 설정한다. (10억)

# n : 노드의 수 / m : 간선의 수
n, m = map(int, input().split())

# start : 시작노드
start = int(input())

# 노드정보
graph = [[] for _ in range(n+1)]

# 방문정보
visited = [False] * (n+1)

# 최단 거리 테이블 (무한으로 초기화)
distance = [INF] * (n+1)

# 모든 간선 정보 입력받기
for _ in range(m):
    a, b, c = map(int, input().split()) # a -> b (비용 c)
    graph[a].append((b, c))

# 가장 최단거리가 짧은 노드 반환 (방문하지 않은 노드 중)
def find_closest_node():
    min = INF # 최단거리의 최솟값
    index = 0 # 최단거리가 가장 짧은 node의 인덱스
    for i in range(1, n+1):
        if distance[i] < min and not visited[i]: # 만약 최단거리가 min보다 짧고 방문하지 않았으면
            min = distance[i] # min 갱신
            index = i # index 갱신
    return index

def dijkstra(start):
    # 시작 노드 초기화
    distance[start] = 0
    visited[start] = True
    
    for j in graph[start]:
        distance[j[0]] = j[1]
    
    # 나머지 노드 루프
    for i in range(n-1):
        v = find_closest_node() # 
        visited[v] = True

        for j in graph[v]:
            cost = distance[v] + j[1]
            if cost < distance[j[0]]:
                distance[j[0]] = cost

dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF:
        print("node ",i," can not visit")
    else:
        print("node ",i," : ", distance[i])

 

입력 예시	출력 예시
6 11 1 1 2 3 1 3 5 1 4 1 2 3 3 2 4 2 3 2 3 3 6 5 4 3 3 4 5 1 5 3 1 5 6 2	node  1  :  0 node  2  :  3 node  3  :  3 node  4  :  1 node  5  :  2 node  6  :  4

 

위 코드를 보면 알 수 있듯이

dijkstra() 안에서

    for i in range(n-1):
        v = find_closest_node() # 
        visited[v] = True

        for j in graph[v]:
            cost = distance[v] + j[1]
            if cost < distance[j[0]]:
                distance[j[0]] = cost

n+1 번 도는 for문 내에서 다시 find_closest_node() 를 호출하는데,

이 메소드에서도 역시 n+1번 도는 for문을 수행한다. ( 소스코드에서 변수 n 은 노드의 수 V )

# 가장 최단거리가 짧은 노드 반환 (방문하지 않은 노드 중)
def find_closest_node():
    min = INF # 최단거리의 최솟값
    index = 0 # 최단거리가 가장 짧은 node의 인덱스
    for i in range(1, n+1):
        if distance[i] < min and not visited[i]: # 만약 최단거리가 min보다 짧고 방문하지 않았으면
            min = distance[i] # min 갱신
            index = i # index 갱신
    return index

find_closest_node() 에서 최단거리 min 값을 구하기 위해 다시 리스트를 n+1회 (약 V ) 순차탐색 해야한다는 것이다.

따라서 시간복잡도가 O(V^2) 로 높다.

 

이를 해결하기 위한 것이 개선된 다익스트라 알고리즘이다.

 

 

구현 2 : 개선된 다익스트라 알고리즘 - O(E log V)

 

개선된 다익스트라 알고리즘은  O(E log V) 의 시간복잡도를 가진다. ( E : 간선의 개수 , V : 노드의 개수 )

간단한 다익스트라 알고리즘에서는 리스트를 매번 순차탐색하였다.

그러나 개선된 알고리즘에서는 힙 (Heap) 자료구조를 활용하여 시간복잡도를 줄인다.

가장 작은 최단거리를 반환하기 위해 최소 힙 기반의 우선순위 큐 를 사용한다.

 

우선순위 큐 구현 방식	삽입	삭제
리스트	O(1)	O(N)
힙 (Heap)	O(logN)	O(logN)

 

 

# 개선된 다익스트라 알고리즘 코드 (O(ElogV))
import heapq, sys
input = sys.stdin.readline
INF = int(1e9)

# n : 노드의 수 / m : 간선의 수
n, m = map(int, input().split())

# start : 시작노드
start = int(input())

# 노드정보
graph = [[] for _ in range(n+1)]

# 방문정보
visited = [False] * (n+1)

# 최단 거리 테이블 (무한으로 초기화)
distance = [INF] * (n+1)

# 모든 간선 정보 입력받기
for _ in range(m):
    a, b, c = map(int, input().split()) # a -> b (비용 c)
    graph[a].append((b, c))

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, v = heapq.heappop(q)
        if distance[v] < dist:
            continue
        for i in graph[v]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF:
        print("node ",i," can not visit")
    else:
        print("node ",i," : ", distance[i])

 

입력과 출력 예시는 간단한 다익스트라 알고리즘과 같다.

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, v = heapq.heappop(q) # 최단거리가 가장 짧은 노드 반환
        if distance[v] < dist: # 현재 노드가 이미 처리되었으면
            continue # 건너뛰기
        for i in graph[v]: # 현재 노드와 연결된 노드 확인
            cost = dist + i[1]
            if cost < distance[i[0]]: # 현재 노드를 거치는 게 더 빠를 경우
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

간단한 알고리즘과 비교하여 변경된 부분은 heapq를 사용하는 부분이다.

find_closest_node 메소드를 사용할 필요 없이 최소 힙을 활용하여 가장 짧은 노드를 반환한다.

그리고 현재 방문한 노드에 연결된 노드의 최단거리를 검사하여 최단거리 테이블 distance 를 갱신한다.

 

 

다익스트라 알고리즘 시간복잡도 정리

 

다익스트라 알고리즘 시간복잡도

두번째 방법을 사용하자..

 

---

참고자료

 

slideplayer.com/slide/4318769/

1 Paths in Graphs Oscar Miguel Alonso M. 2 Outline The problem to be solved Breadth first search Dijkstra's Algorithm Bellman-Fo