[알고리즘] 다익스트라 최단 경로 알고리즘 파이썬 구현

자료 출처: https://youtu.be/acqm9mM1P6o

동빈북을 사두고 생각보다 어려워서 많이 못 봤는데, 이 강의 시리즈를 보다보니 이해가 쉽게 가고 재밌어서 대강 쭉 봤다. 요즘 블로그에 정리하는 내용들도 강의 요약본이나 마찬가지인데, 어려운 알고리즘들은 계속 읽어보며 완전히 이해가 될 때까지 못 넘기겠어서 하나하나 코멘트를 다는 중. 투머치이긴 하지만 내가 이해하기 위한 것이기 때문에 그냥 적으려 한다.

1. 최단 경로 알고리즘 개요

• 한 지점에서 다른 한 지점까지
• 한 지점에서 다른 모든 지점까지: 다익스트라 알고리즘
• 모든 지점에서 다른 모든 지점까지: 플로이드 워셜 알고리즘
• 이 때 각 지점은 노드로, 지점 간을 연결하는 도로는 간선으로 표현한다.

2. 다익스트라 최단 경로 알고리즘

특정 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산

• 음의 간선이 없을 때 정상적으로 동작한다. 현실 세계의 도로(간선)는 음의 간선으로 분류되지 않기 때문에 현실 세계의 길 찾기 문제에서 활용됨
• 그리디 알고리즘으로 분류: 탐욕적인 원리를 이용하여 매 상황마다 가장 비용이 적은 노드를 선택하고 임의의 과정을 반복하기 때문
• 한 노드에서 다른 모든 노드까지의 최단 경로 (플로이드 워셜 알고리즘과의 차이점 - 모든 노드에서 다른 모든 노드까지의 최단 경로)

3. 동작 과정

• 출발 노드 설정: 출발 노드는 하나로, 앞으로 이 노드에서 다른 모든 노드까지의 최단 거리를 찾아주는 과정임
• 최단 거리 테이블 초기화: 자기 자신에 대한 비용은 0, 나머지에 대한 비용은 무한대로 설정
• 방문하지 않은 노드 중 최단 거리 가장 짧은 노드 선택 → 이 과정을 반복할 때마다 그렇게 선택된 노드까지의 최단 거리는 더이상 바뀌지 않음
• (출발노드에서) 해당 노드 거쳐 다른 노드로 가는 비용 계산, 최단 거리 테이블 갱신
• 위의 두 과정(3, 4번째) 반복

알고리즘 동작 과정에서 최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가지고 있다. → 처리 과정에서 더 짧은 경로를 찾으면 "이제부터는 이 경로가 제일 짧은 경로다"라고 갱신

4. 다익스트라 알고리즘의 특징

• 그리디 알고리즘: 매 상황에서 방문하지 않은 노드 중 가장 비용이 적은 노드를 선택한다.
• 단계를 거치며 한 번 처리된 노드의 최단거리는 고정되어 더이상 바뀌지 않는다. → 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것이라고 할 수 있다.
• 수행 후 테이블에 각 노드까지의 최단 거리 정보가 저장된다.

5. 다익스트라 알고리즘의 간단한 구현

inf = int(1e9) # 무한대를 나타내는 큰 값

# 노드의 개수, 간선의 개수, 시작 노드를 입력받는다.
n, m, start = map(int, input().split())

# 모든 노드에 대하여 각 노드에 연결된 노드들에 대한 정보를 담기 위해 중첩 리스트로 초기화해준다.
# (n + 1)인 이유는 노드 넘버라 1부터 세기 때문
graph = [[] for _ in range(n + 1)]

visited = [False] * (n + 1)

# 최단거리 테이블로, 전부 무한으로 초기화한다. 여기서 거리는 시작 노드부터의 거리를 의미한다.
distance = [inf] * (n + 1)

# 모든 간선에 대하여, 간선 각각의 연결 정보(어떤 노드에서 또 다른 어떤 노드로 얼마의 비용으로 연결되는지)를 graph에 업데이트한다.
for _ in range(m):
    a, b, c = map(int, input().split()) # a번 노드에서 b번 노드로 가는 비용이 c
    
    # 여기서 a는 숫자로 인덱스를 나타내며, graph가 중첩리스트이기 때문에 외부 리스트에서 인덱스값이 a인 내부 리스트에 대하여
    # 해당 내부 리스트에 (b, c) 튜플을 append해준다.
    # 즉 a노드에 연결된 노드들(b들)과 그 비용(c들)을 인덱스가 a인 내부 리스트에 튜플 형태로 저장한다는 것
    graph[a].append((b, c))
    

# 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드의 번호를 반환하는 함수
def get_smallest_node():

    min_val = inf
    min_index = 0 # 최단 거리가 가장 짧은 노드의 인덱스
    
    for i in range(1, n + 1): # 모든 노드들에 대하여(1번부터 n번까지의 모든 노드 확인)
        if distance[i] < min_val and not visited[i]: # distance[i]는 시작노드부터 i 노드까지의 최단 거리
            min_val = distance[i]
            min_index = i
    
    return min_index
    
    
def dijkstra(start):

    # 시작 노드 초기화와 방문 처리
    distance[start] = 0
    visited[start] = True
    
    # graph는 중첩 리스트
    # graph에서 start 노드에 연결된 모든 노드와 비용(튜플)에 대하여
    for node, dist in graph[start]:
        # 시작 노드부터 해당 노드까지의 거리를 업데이트해준다.
        distance[node] = dist
    
    # 시작 노드를 제외한 (n - 1)개의 노드에 대하여 반복 수행
    # 무엇을 반복 수행하는가?
    # 시작 노드에서 직접 가는 비용 vs i 노드를 거쳐서 가는 비용을 비교하여 최단 거리를 업데이트한다.
    for i in range(n - 1):
    
        # 현재 최단 거리가 가장 짧은 노드를 꺼내어 방문 처리한다.
        now = get_smallest_node()
        visited[now] = True
        
        # 현재 노드와 연결된 다른 노드-비용(튜플)을 확인한다.
        # 왜 확인?
        # 현재 노드를 거쳐서 가는 경우에 최단 거리가 더 짧다면 이를 업데이트하기 위해서임.
        for node, dist in graph[now]:
        
            # 비용 = (시작 노드에서부터 현재 노드까지의 거리) + (현재 노드로부터 다른 노드까지의 거리)
            # 즉, 현재 노드를 거쳐 다른 노드로 가는 경우의 비용을 계산한 것이 cost
            cost = distance[now] + dist
            
            # cost(현재 노드를 거쳐서 다른 노드로 이동하는 거리)가 기존의 다른 노드까지의 최단 거리보다 짧다면
            if cost < distance[node]:
                distance[node] = cost # 갱신해준다.
                

dijkstra(start)

for i in range(1, n + 1):
    if distance[i] == inf:
        print("infinity")
    else:
        print(distance[i])

성능 분석

• 총 O(V)번에 걸쳐 최단 거리가 가장 짧은 노드를 매번 선형 탐색하므로 O(V^2)의 시간 복잡도를 갖는다.
• 전체 노드 개수가 5000 이하면 이 코드로 해결이 가능하다.

6. 다익스트라 알고리즘의 개선된 구현

• 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 힙 자료구조를 이용한다.
• 힙에 원소를 넣을 때 거리 기준으로 넣는다.
• 알고리즘의 기본 원리는 동일
  • 현재 가장 가까운 노드를 저장해놓기 위해 힙 자료구조를 사용한다는 점이 다르다.
  • 최단 거리가 가장 짧은 노드를 선택해야 하므로 최소 힙을 사용한다. (최소 힙의 경우, 값이(=거리가) 가장 작은 데이터부터 제거되기 때문)

import heapq

inf = int(1e9)

n, m, start = map(int, input().split())

graph = [[] for _ in range(n + 1)] # (n + 1)인 이유는 노드 넘버라 1부터 시작하기 때문
distance = [inf] * (n + 1) # 여기서 거리는 시작 노드로부터의 거리를 의미

# 다익스트라 함수에서 따로 방문된 경우를 체크해줄 것이기 때문에 visited는 별도로 필요하지 않음

for _ in range(m): # 모든 간선에 대하여
    a, b, c = map(int, input().split()) # a번 노드에서 b번 노드로 가는 비용이 c
    # a는 인덱스로, 외부 리스트에서 인덱스가 a인 내부 리스트에 (b, c) 튜플을 append해줌
    graph[a].append((b, c))
    

def dijkstra(start):
    
    q = [] # 우선순위 큐 생성 (우선순위(=최단거리)가 가장 높은 데이터를 가장 먼저 삭제) 
    heapq.heappush(q, (0, start)) # 최소 힙에 (거리, 노드) 쌍을 push해주는데, 거리 기준으로 삽입됨
    distance[start] = 0 # 시작 노드에서 시작 노드로 가는 거리는 0
    
    while q:
    
        # 최소 힙에서 최단 거리가 가장 짧은 노드의 거리값과 노드 꺼냄
        # 최소 힙이기 때문에 값이 가장 작은 데이터(=거리가 가장 짧은 데이터) 먼저 꺼냄
        dist_now, node_now = heapq.heappop(q)
        
        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시한다.
        # 이때 별도의 방문 처리가 필요하지 않음
        # 현재 꺼낸 원소의 거리값이 distance 테이블에 기록된 값보다 크면 이미 처리된 것으로 간주하기 때문
        # 즉, 이미 최단 거리를 찾은 것으로 볼 수 있다.
        if distance[node_now] < dist_now:
            continue
            
        # 현재 노드와 연결된 다른 인접한 노드들 확인
        for node, dist in graph[node_now]:
        
            # 시작 노드에서 현재 노드를 거쳐서 인접 노드로 가는 비용 = (시작 노드에서 현재 노드까지의 거리) + (현재 노드에서 인접 노드로 가는 거리)
            cost = dist_now + dist
            
            # 시작 노드에서 현재 노드를 거쳐서 인접 노드로 이동하는 거리가 기존 인접 노드의 거리값보다 더 짧은 경우
            if cost < distance[node]:
                distance[node] = cost # 갱신
                heapq.heappush(q, (cost, node)) # 값이 갱신될 때마다 우선순위 큐에 기록

성능 분석

• 힙 자료구조 이용시 시간 복잡도: O(ElogV)
• 노드를 하나씩 꺼내 검사하는 while문은 노드의 개수(V) 이상으로는 처리하지 않는다(이미 처리된 노드는 무시하기 때문).
• 결과적으로 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총 횟수는 최대 간선의 개수(E) 만큼 연산 수행
• 직관적으로 E개의 원소를 우선순위 큐에 넣었다 빼내는 연산과 유사
  • O(ElogE)
  • O(ElogE) → O(ElogV^2) → O(2ElogV) → O(ElogV)