[Python] Dijkstra(다익스트라)

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

음의 가중치가 없는 그래프의 한 정점(Vertex)에서 모든 정점까지의 최단거리를 구하는 알고리즘

특징

• 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복(Greedy)
• 가중치가 음수인 경우 다익스트라 알고리즘은 사용할 수 없으며, 이 경우 Floyd-Warshall 알고리즘으로 해결할 수 있음.
  (단, 음의 사이클이 존재하는 경우 음의 무한대로 발산하므로 사용 불가)
• 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않음
• 다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보가 저장
• 시간 복잡도 : $O(V^2)$ → 개선된 다익스트라의 경우 $O((V+E)logV)$
  (V : 노드의 개수, E : 간선의 개수)
  

동작 과정

1. 출발 노드 설정
2. 각 노드별 최단 거리를 저장할 배열 초기화
3. 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 배열 갱신
5. 위 3~4번을 반복

구현

기존 다익스트라 알고리즘

• 시간 복잡도 : $O(V^2)$

def select_via(): # 사용되지 않은 원소 중 가장 작은 원소를 via로 선택
    Min = int(21e8)
    for i in range(n):
        if used[i]==0 and result[i] < Min:
            Min = result[i]
            Minindex = i
    return Minindex

def dijkstra():
    for i in range(n-1):
        via_idx = select_via() # 경유할 포인트 선정
        used[via_idx] = 1
        for j in range(n):
            direct = result[j] 
            via = result[via_idx] + arr[via_idx][j]
            if direct > via:
                result[j]=via
        print(*result)

inf = int(21e8)
arr = [
    [0, 3, inf, 9, 5],
    [inf, 0, 7, inf, 1],
    [inf, inf, 0, 1, inf],
    [inf, inf, inf, 0, inf],
    [inf, inf, 1, inf, 0],
]
n = len(arr)
used = [0]*n
result = [0]*n
start, end = map(int, input().split())
for i in range(n):
    result[i] = arr[start][i]
used[start]=1

dijkstra()
print(*result)

개선된 다익스트라

• heapq를 사용
• 시간 복잡도 : $O((V+E)logV)$

import heapq

def dijkstra(start):
    # heapq.heappush(heap, (비용, 경유노드))
    heapq.heappush(heap, (0, start)) # 처음에는 시작노드를 경유노드로 놓기 
    result[start]=0                  # 그 다음 부터는 heapq에서 최소 비용을 다음 경유노드로 선택

    while heap:
        dist, node = heapq.heappop(heap)  
        # dist : 시작노드에서 경유노드 까지 비용
        # node : 경유 노드

        if result[node] < dist: continue    
        # result에 업데이트 된 비용(시작->경유)과 큐에서 뽑은 비용(시작->경유)을 비교
        for next in arr[node]:     # 모든 정점에 대해서 (경유지에서 도착할 수 있는 정점) 비교
            cost = dist+next[1]    
            # cost : 비용(시작->경유) + 비용(경유->도착)
            # next : [0: 노드, 1: 비용]
            if cost < result[next[0]]:
                result[next[0]] = cost
                heapq.heappush(heap, (cost, next[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))
start, end = map(int, input().split())
inf = int(21e8)
result = [inf]*n    # 각 노드별 최소비용을 저장할 result 리스트 초기화
heap = []
dijkstra(start)
print(*result)

'''
test case
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
'''