최단 경로 알고리즘(다익스트라)

최단 경로란?

 

가장 짧은 거리를 찾는 알고리즘

그래프가 주어졌을 때 특정 노드에서 다른 노드까지의 최단 거리를 구할 때 사용

 

경로 계산 방식에는 3가지 종류가 존재

 

1. One-To-One : 한 지점에서 다른 특정 지점까지의 최단경로

2. One-To-All : 한 지점에서 다른 모든 지점까지의 최단경로

3. All -To -All : 모든 지점에서 모든 지점까지의 최단경로

 

다익스트라 알고리즘

 

- 위의 경로 계산 방식 중 2번째 One-To-All의 대표적인 방법

- 음의 간선이 없을 때 정상적으로 작동

- 매 상황에서 가장 비용이 적은 노드를 선택(그리디 알고리즘으로 분류)

 

동작 과정

 

1. 출발 노드 설정

2. 최단 거리 테이블 초기화

3. 방문하지 않은 노드 중에서 최단거리 노드 선택

4. 해당 노드를 거쳐 다른 노드로 가는 비용 계산 후 최단 거리 테이블 갱신

5. 3번 4번 과정 반복

 

1번 노드에서 시작해서 모든 정점까지의 최단 경로를 구한고 가정

노드들 간의 가중치는 그림과 같고 distance 배열은 1번 정점에서 특정 점정까지의 최단 경로 길이를 나타냄

초기에는 최단경로를 구하지 않은 상태이므로 무한대로 표시

 

distance[특정 노드]과 distance[1] + (1번 노드와 특정 노드 사이 가중치)를 비교해 더 작은 값으로 distance[특정 노드] 업데이트

 

 

n, m = 6, 9     # 노드의 개수, 간선의 개수
start = 1       # 시작 노드

# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
graph = [[] for i in range(n + 1)]

# 모든 노드, 간선 정보 입력받기
# [노드번호, 거리]
graph = [
    [],
    [[2, 7], [3, 9], [6, 14]],
    [[3, 10], [4, 15]],
    [[4, 11], [6, 2]],
    [[5, 6]],
    [[6, 9]],
    [],
]

# 무한대, 1e9(10억) 처럼 그냥 큰 수로도 많이 초기화함
INF = float("inf")

# 방문한 적이 있는지 체크하는 목적의 리스트
visited = [False] * (n + 1)  # [False, False, False, False, False, False, False]

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


# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
def get_smallest_node():
    index = 0   # 가장 최단 거리가 짧은 노드 (인덱스)
    for i in range(1, n + 1):
        if distance[i] < distance[index] and not visited[i]:
            index = i
    return index


def dijkstra(start):
    # 시작 노드에 대해서 초기화
    distance[start] = 0
    visited[start] = True
    for node, dist in graph[start]:
        distance[node] = dist
    
    # 시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
    for _ in range(n - 1):
        # 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
        now = get_smallest_node()
        visited[now] = True

        # 현재 노드와 연결된 다른 노드를 확인
        for node, dist in graph[now]:
            cost = distance[now] + dist  # 현재 노드까지의 거리 + 다음 노드까지의 거리
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짭은 경우
            if cost < distance[node]:
                distance[node] = cost


# 다익스트라 알고리즘 수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
print(*distance[1:])

 

다익스트라 알고리즘 문제점

 

- O(v^2)의 시간 복잡도

- 매 단계마다 모든 노드를 순회하며 최단 거리 노드를 찾아야함

 

이러한 문제점을 heap 자료구조를 이용하여 개선할 수 있다

 

*자료구조

 

- 스택(Stace) : 선입후출

- 큐(Queue) : 선입선출

- 힙(Heap) : 우선순위가 높은 데이터를 먼저 추출(우선순위 큐)

 

Heap(우선순위 큐)

 

- 우선순위가 가장 높은 데이터를 가장 먼저 처리하는 자료구조

- 다익스트라 알고리즘의 성능을 개선하기 위해 사용

- 최소 힙(Min Heap)과 최대 힙(Max Heap)이 있음

- 파이썬에서는 기본 최소 힙 구조 사용

 

import heapq

# 오름차순 힙 정렬 (Heap Sort, 최소 힙)
def heapsort(iterable):
    h = []
    for i in iterable:
        heapq.heappush(h, i)
    return [heapq.heappop(h) for _ in range(len(h))]

result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

def heapsort2(iterable):
    h = []
    for i in iterable:
        heapq.heappush(h, -i)
    return [-heapq.heappop(h) for _ in range(len(h))]

result2 = heapsort2([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result2)

 

다익스트라 알고리즘 개선

 

- 기본 구조는 똑같으나 최단 거리를 Heap으로 관리한다는 차이만 존재

- 시간 복잡도 개선: O(v^2) -> O(ElogV) # NOTE. E: Edge, V: Vertex

- 파이썬에서는 heapq 라이브러리 이용 가능

 

import heapq

n, m = 6, 9     # 노드의 개수, 간선의 개수
start = 1       # 시작 노드

# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
graph = [[] for i in range(n + 1)]

# 모든 노드, 간선 정보 입력받기
# [노드번호, 거리]
graph = [
    [],
    [[2, 7], [3, 9], [6, 14]],
    [[3, 10], [4, 15]],
    [[4, 11], [6, 2]],
    [[5, 6]],
    [[6, 9]],
    [],
]

INF = float('inf')

# 방문 여부는 heap안에 있냐 없냐로 판단이 가능하기 때문에 따로 기록할 필요가 없음
# visited = [False] * (n + 1)

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


def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입 (거리, 노드번호)
    # 거리를 앞에 두는 이유는 거리순으로 큐에 삽입하기 위해서임
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop(q)
        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
        if distance[now] < dist:
            continue
        # 현재 노드와 연결된 다른 인접한 노드들을 확인
        for node, dist2 in graph[now]:
            cost = dist + dist2
            # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[node]:
                distance[node] = cost
                heapq.heappush(q, (cost, node))
            

# 다익스트라 알고리즘 수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
print(*distance[1:])

동작 방식은 동일하지만 별도의 방문 처리 리스트 visited가 필요하지 않다

 

SPFA

 

- 가중치가 음수인 경우 다익스트라 알고리즘으로 해결 불가능!

- 시간 복잡도 : O(E*V), 하지만 실제로는 O(E) 정도의 성능

- 다익스트라와 달리, 음수 간선에도 사용 가능

- 벨만포드 알고리즘과 같은 아이디어지만 월등히 좋은 성능

- 벨만포드는 모든 간선에 대해 업데이트 진행, SPFA는 바뀐 노드과 연결된 간선에 대해서만 업데이트를 진행, 따라서 실제 코딩테스트나 대회에서는 벨만포드를 사용하지 않음

 

from collections import deque

v, e = 5, 8    # 노드의 개수, 간선의 개수
start = 1
array = [[1, 2, 1],  # from, to, weight
         [2, 3, 7], 
         [2, 4, -2], 
         [1, 3, 8], 
         [1, 4, 9], 
         [3, 4, 3], 
         [2, 5, 3], 
         [4, 5, -3]]

# 그래프 초기화
graph = [[] for _ in range(v + 1)]
for frm, to, dist in array:
    graph[frm].append((to, dist))

# 거리 정보 초기화 (시작위치: 0)
distance = [float('inf')] * (v + 1)
distance[start] = 0

# SPFA 수행
q = deque([start])
while q:
    now = q.popleft()
    for node, dist in graph[now]:
        cost = distance[now] + dist
        if cost < distance[node]:
            distance[node] = cost
            q.append(node)

print(*distance[1:])  # 0 1 8 -1 -4