[Algorithm] / [Python] 다익스트라 (Dijkstra)

1. 다익스트라 (Dijkstra) ?

최단 경로를 구하는데 사용되는 알고리즘 중 하나입니다.

즉, 한 지점에서 다른 한 지점까지의 최단 경로

한 지점에서 다른 모든 지점까지의 최단 경로

모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 알고리즘입니다.

자료구조로는 Graph를 사용하며, 노드(vertex)와 경로 또는 거리 는 간선(edge)을 사용하여 실제 거리를 표현합니다.

 

2. 다익스트라 알고리즘의 과정

다익스트라 알고리즘은 매번 가장 거리가 짧은 노드를 선택해서 정해진 경로에 따라 과정을 계속적으로 반복하게 됩니다.

1. 출발 노드를 지정
2. 최단 거리 리스트 초기화 (매번 최단 기록 갱신)
3. 방문하지 않은 노드 중 가장 거리가 짧은 노드 선택
4. 해당 노드 방문 후 다른 노드로 가는 거리를 계산 후 최단 거리 갱신
5. 위 과정 중 3, 4번을 방문할 노드가 없을 때까지 반복

 

초기 단계

시작 노드를 1번 빨간색으로 지정합니다. 

아래의 리스트는 각 노드간의 거리를 나타냅니다.

 

2 단계

1번 노드부터 접근할 수 있는 노드들의 거리를 리스트에 업데이트합니다.

 

3 단계

1번 노드를 방문처리 하고 1번 노드의 인접한 노드의 방문하지 않은 노드 중 최단 거리인 4번 노드를 탐색할 노드로 선택합니다.

탐색할 4번 노드는 3번과 5번 노드에 연결되어 있습니다. 여기서 \(min(5, 1+3)\) 중 5는 2 단계 에서 갱신한 1번과 3번 노드의 거리입니다. 1+3은 1번과 4번 노드의 거리 1과 4번과 3번 노드의 거리 3을 의미합니다. 이 2개의 경로 중 최단 거리는 1번에서 3번으로 바로 가는 것 보다 1번에서 4번을 거치고 3번으로 가는 경로가 최단 거리이기 때문에 3번 노드로 가는 경우를 업데이트 합니다. 

 

다음으로 방문할 노드 중 가장 거리가 짧은 노드를 선택하는데, 거리가 같은 경우 노드가 작은 곳부터 먼저 방문합니다.

 

4 단계

이후 최단 거리를 갱신하는 과정을 계속해서 진행합니다.

 

3. 다익스트라 알고리즘을 Python으로 구현하기

간단한 다익스트라 알고리즘은 \(V\)가 노드의 개수라고 가정할 때, 시간 복잡도가 \(O(V^2)\)가 됩니다.

왜냐하면 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 떄문에, 매 단계마다 거리와 인접한 노드의 개수 만큼 순차탐색을 수행하기 때문입니다.

import sys
input = sys.stdin.readline
INF = float('inf')

n, m = map(int, input().split())
start = int(input()) # 시작할 노드

graph = [[] for _ in range(n+1)]

visited = [False] * (n+1)  # 방문처리 기록용
distance = [INF] * (n+1)   # 거리 테이블용

# a : 출발노드, b: 도착노드, c: 거리
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

# 방문하지 않은 노드 and 시작노드와 최단거리인 노드 반환
def get_smallest_node():
    min_value = INF
    index = 0
    for i in range(1, n+1):
        if not visited[i] and distance[i] < min_value:
            min_value = distance[i]
            index = i
    return index

# 다익스트라 알고리즘
def dijkstra(start):
    # 시작노드 init
    distance[start] = 0
    visited[start] = True
    
    # 시작노드의 인접한 노드들에 대해 최단거리
    for i in graph[start]:
        distance[i[0]] = i[1]

    # 시작노드 제외한 n-1개의 다른 노드들 처리
    for _ in range(n-1):
        now = get_smallest_node()  # 방문X 면서 시작노드와 최단거리인 노드 반환
        visited[now] = True        # 해당 노드 방문처리
        
        # 해당 노드의 인접한 노드들 간의 거리 계산
        for next in graph[now]:
            cost = distance[now] + next[1]  # 시작->now 거리 + now->now의 인접노드 거리
            if cost < distance[next[0]]:    # cost < 시작->now의 인접노드 다이렉트 거리
                distance[next[0]] = cost

dijkstra(start)
print(distance[i])
        
# 5 6
# 1
# 5 1 1
# 1 2 1
# 1 3 3
# 2 3 1
# 2 4 5
# 3 4 2

heap 으로 구현

n, m = map(int, input().split())
k = int(input())                 # 시작할 노드
INF = float('inf')

graph = [[] for _ in range(n+1)]

distance = [INF] * (n+1)

for _ in range(m):
  u, v, w = map(int, input().split()) # u: 출발노드, v: 도착노드, w: 연결된 간선의 가중치 
  graph[u].append((v, w))             # 거리 정보와 도착노드를 같이 입력합니다.

import heapq

def dijkstra(start):
  q = []
  heapq.heappush(q, (0, start)) # 우선순위, 값 형태로 들어간다.
  distance[start] = 0

  while q:
    dist, now = heapq.heappop(q) # 우선순위가 가장 낮은 값(가장 작은 거리)이 나온다.

    if distance[now] < dist: # 이미 입력되어있는 값이 현재노드까지의 거리보다 작다면 이미 방문한 노드이다.
      continue               # 따라서 다음으로 넘어간다.

    for i in graph[now]:     # 연결된 모든 노드 탐색
      if dist+i[1] < distance[i[0]]: # 기존에 입력되어있는 값보다 크다면
        distance[i[0]] = dist+i[1]   #
        heapq.heappush(q, (dist+i[1], i[0]))
        
dijkstra(k)
print(distance)

# 5 6
# 1
# 5 1 1
# 1 2 1
# 1 3 3
# 2 3 1
# 2 4 5
# 3 4 2

---

프로그래머스 적용

 

https://school.programmers.co.kr/learn/courses/30/lessons/12978

프로그래머스

 

 

---

참고 사이트

 

https://techblog-history-younghunjo1.tistory.com/247

[Python] 최단경로를 위한 다익스트라(Dijkstra) 알고리즘

https://youtu.be/F-tkqjUiik0