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

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

다익스트라 알고리즘은 플로이드 워셜(Floyd-Warshall)과 함께 최단 경로를 찾는 대표적인 알고리즘이다. 다익스트라는 구현이 간단하지만 오래 걸리는 방법과 구현은 복잡하지만 성능이 개선된 방법 두 가지가 존재한다.

다익스트라의 특징

• 시작점에서 도착점(특정 노드 또는 모든 노드)까지의 최소 비용을 구할 때 사용한다.
• 단, 가중치가 음수일 경우 사용하지 못한다.
  • 가중치가 음수일 때는 벨만-포드 알고리즘(Bellman-Ford Algorithm)이 사용 가능한데 이 경우에도 제약 사항이 존재한다. (음의 사이클이 존재하면 사용하지 못한다.)
• 원래는 O(V^2)의 시간복잡도를 가진다. 하지만 heapq(우선순위 큐)를 사용하면 O(ElogV)의 속도로 개선 가능하다. 이를 개선된 다익스트라라고 부른다.
  • V: 노드의 개수, E: 간선의 개수
    참고: https://techblog-history-younghunjo1.tistory.com/248

💡다익스트라 동작 방식

1. 출발 노드를 설정
2. 최단 거리 테이블을 inf(아주 큰 값)으로 초기화
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
   1. 방문 여부를 나타내기 위한 visited 배열이 필요
4. 해당 노드를 경유지로 삼아 다른 노드로 가는 비용을 계산하여 다이렉트로 가는 비용보다 작을 시 최단 거리 테이블을 업데이트
5. 위 과정에서 3, 4번을 반복

순차 탐색으로 구현

# 시작점-도착점 바로 가는 거랑 시작점-경유지-도착점 비용 비교해서, 작은 것으로 업데이트
st, ed = 0, 4
arr = [
    [0,3,21e8,9,5], # 연결되어 있지 않은 노드는 21e8로 초기화
    [21e8,0,7,21e8,1],
    [21e8,21e8,0,1,21e8],
    [21e8,21e8,21e8,0,21e8],
    [21e8,21e8,1,21e8,0]
]
used = [0]*5
result = arr[0][:] # 최단 거리 테이블 초기화
used[st] = 1 # 시작점을 방문 처리

for _ in range(len(arr)-1): # 경유지를 총 N-1번 고르면서 바꿔감

    # 경유지로 선택하지 않았던 것 중에 최소 비용을 가지는 노드를 경유지로 선택
    Min, Min_idx = 21e8, 0 
    for i in range(len(result)):
        if result[i] < Min and used[i] == 0: ## 중요
            Min = result[i]
            Min_idx = i

    mid = Min_idx # 경유지
    used[mid] = 1 # 방문 처리

    for i in range(len(result)):
        dest = i # 도착점

        # direct: 시작점 - 도착점 비용
        direct = result[i]

        # detour: 시작점 - 경유지 - 도착점 비용
        detour = result[mid] + arr[mid][dest]

        if direct > detour: # detour가 더 작을 경우 업데이트
            result[i] = detour
print(*result)
print(result[ed]) # st -> ed의 최단 거리

💡우선순위 큐로 구현

# 개선된 다익스트라
'''
5 정점의 개수
7 간선의 개수
0 1 3 시작점, 도착점, 비용
0 3 9
0 4 5
1 2 7
1 4 1
2 3 1
4 2 1
0 3 최소비용이 알고 싶은 출발점과 도착지 
'''
import heapq

def dijkstra(start):

    # 비용, 경유지/ 적은 비용 순으로 pop하기 위해 이런 순서로 push
    heapq.heappush(heap, (0,start)) 
    result[start] = 0                   # 시작점 최단 거리 초기화
    while heap:
        cost, mid = heapq.heappop(heap) # 시작점 > 경유지 비용, 경유지

        if result[mid] < cost: continue # 업데이트 되어있는 시작점 -> 경유지 값 vs
                                        # 큐에서 방금 뽑은 시작점 -> 경유지 값 비교

        # 경유지에서 갈 수 있는 도착점을 모두 순회
        for i in arr[mid]:  
            detour = cost + i[1]
            if detour < result[i[0]]:
                result[i[0]] = detour
                heapq.heappush(heap, (detour, i[0])) # 갱신된 비용(우선순위), 도착지 

name = 'ABCDE'
N = int(input())
M = int(input())

arr = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    arr[a].append((b,c))          # 도착점, 비용 순으로 append

st, ed = map(int, input().split())
inf = 21e8
result = [inf]*N                  # 최단 거리 테이블 초기화
heap = []

dijkstra(st)
print(*result)

다익스트라 활용 문제

• SWEA
  • 최소 이동 거리