Dijkstra 알고리즘

Dijkstra 알고리즘

Dijkstra 알고리즘이란?

1️⃣ 한 정점에서 다른 모든 도착점까지 드는 최소 비용 or 최단 거리를 구할 때 사용하는 알고리즘

2️⃣ BFS, DFS보다 효율성을 높이고 빠른 속도를 위해 사용

3️⃣ 한 점에서 다른 점까지의 비용에 양수만 존재해야 함. (음수 → Bellmanford)

4️⃣ 양방향, 단방향 모두 가능

Keyword

시작 → 도착 vs 시작 → 경유지 → 도착 비교 후 더 작은 것으로 갱신

코드 구현

name = 'ABCED'
inf = 99999
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]]
used = [0]*5
used[0] = 1  # 시작점 A에 해당하는 used배열에 1 체크
result = [0, 3, inf, 9, 5]

def select_ky():
    minn = inf
    minindex = 0
    for i in range(5):
        if used[i] == 0 and result[i] < minn:
            minn = result[i]
            minindex = i
    return minindex

def dijk():
    for i in range(4):
        via = select_ky()
        used[via] = 1
        for j in range(5):
            baro = result[j]
            kyung = result[via]+arr[via][j]
            if baro > kyung:
                result[j] = kyung
dijk()
print(result)

우선순위 큐 (Priority Queue) 사용

import heapq
n = int(input()) # 정점의 개수
m = int(input()) # 간선의 개수
graph = [[] for _ in range(m)]

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c)) # 도착지, 비용

start, target = map(int, input().split())

inf = 2e18
result = [inf] * n

def dijkstra(start):
    result[start] = 0
    heap = []
    heapq.heappush(heap, (0, start)) # 비용, 경유지

    while heap:
        si_ky_cost, kyungyou = heapq.heappop(heap)
        if si_ky_cost > result[kyungyou]:
            continue
        for i in graph[kyungyou]:
            si_ky_do_cost = si_ky_cost + i[1]
            if si_ky_do_cost < result[i[0]]:
                result[i[0]] = si_ky_do_cost
                heapq.heappush(heap, (si_ky_do_cost, i[0]))
dijkstra(start)
print(result[target])