다익스트라 알고리즘

다익스트라 알고리즘은 최단 경로를 구하는 구하는 알고리즘 중 하나이다.

그래프에서 특정 노드에서 출발하여 다른 모든 노드로 가는 각각의 최단 경로를 구해주는 알고리즘입니다.

각각의 최단 경로를 구하는 과정 속에서 기존의 값과 비교하여 최단 거리로 갱신을 합니다.

또한 음에 간선(길이가 음수인 경우)을 포함하지 않기에 현실 세계에 사용하기 적합합니다.

예시로 네비게이션에서 지도상의 각 도시들간의 최단 거리, 미로탐색등에 사용됩니다.

다익스트라 알고리즘과 플로이드-워셜 알고리즘의 차이는 다익스트라 알고리즘은 하나의 노드로부터 최단경로를 구하고, 플로이드-워셜 알고리즘은 가능한 모든 노드쌍들에 대한 최단거리를 구하는 알고리즘입니다.

예시를 통해 설명을 해드리도록 하겠습니다.

Step 1:

0을 기준으로 탐색을 할 것이기 때문에 0과의 거리를 0이라고 두고 마너지는 infinity로 설정합니다.

추가적으로 인접한 1번 7번과의 거리를 업데이트 합니다.

=> {0, 4, INF, INF, INF, INF, INF, 7, INF}

Step 2:

1번의 다른 방법으로의 최단거리는 7번을 통한 방법밖에 없는데 길이가 8로 4보다 크므로 1번과의 최단거리가 4임을 확정할 수 있습니다.

Step 3:

7번의 최단거리 또한 1번을 통한 길이와 비교했을 때
0 -> 7 이 0 -> 1 -> 11보다 가까우므로 7사이의 최단거리가 8임을 확정합니다.

Step 4:

앞에와 마찬가지로 연결되어 있는 노드들 간의 거리를 계산하여서 최적의 값들로 업데이트 합니다.

알고리즘 코드

import heapq
import sys

def dijkstra(start):
    distances = {node: sys.maxsize for node in graph}
    distances[start] = 0     
    queue = []
    heapq.heappush(queue, (distances[start], start))


    while queue:
        current_distance, node = heapq.heappop(queue)
        if distances[node] < current_distance:
            continue

        for ad_node, distance in graph[node].items():
            weighted_distance = current_distance + distance
            if weighted_distance < distances[ad_node]:
                distances[ad_node] = weighted_distance
                heapq.heappush(queue, (weighted_distance, ad_node))

    return distances

graph = {
    '0': {'1': 4, '7': 8},
    '1': {'0': 4, '2': 8, '7' : 11},
    '2': {'1': 8, '3': 7, '5': 4, '8' : 2},
    '3': {'2': 7, '4': 9, '5': 14},
    '4': {'3': 9, '5': 10},
    '5': {'2': 4, '3': 14, '4': 10},
    '6': {'5': 2, '7': 1, '8': 6},
    '7': {'0': 8, '1': 11, '6': 1},
    '8': {'2': 2, '6': 6, '7': 7},
}

n = int(input()) # 기준이 될 숫자
ans = dijkstra(str(n))
print(ans)

사진 구했던 사이트에서 코드도 나와있는데 queue로 Big_O값을 n log n으로 했고, 파이썬의 특징인 dictionary를 활용하여서 알고리즘을 구현했습니다.
링크텍스트