새싹프로그래머의 이야기

*알고리즘 이론은 복습 용도로 작성되었습니다. 간략하게 작성되어 있을 수 있으며 해당 알고리즘을 어느정도 알고있다는 전제하에 작성되었습니다.

다익스트라(dijkstra) 알고리즘은 최단 경로를 구하는 알고리즘 중 하나입니다.

1. 최단 경로(Shortest Path) 알고리즘이란?

Path와 cost가 주어졌을 때, cost가 제일 적게 드는 경로를 찾는 알고리즘 입니다.

특히, 다익스트라 알고리즘은 한 지점에서 특정 지점까지의 최단 경로를 구하는 알고리즘으로 시작점과 끝점을 필요로 합니다.

자료구조로는 graph를 사용하며, 지점을 그래프의 node로 표현하고 경로를 그래프의 edge로 표현합니다.

2. 다익스트라 알고리즘

1. 시작 노드가 1이라고 했을 때, 알고리즘이 동작하는 원리는 다음과 같습니다.
2. 1에서 cost가 가장 가까운 노드 3에 대한 distance를 업데이트 합니다
3. 1에서 가장 가까운 노드를 모두 업데이트 합니다. 즉, 1에 대해서 1 -> 3, 1 -> 2, 1 -> 5 의 cost가 업데이트 됩니다.
4. 코스트가 낮은 3으로 이동하지만 연결된 노드가 없으므로, 2로 이동합니다.
5. 2 -> 5의 cost = 1이므로, 1 -> 5 의 최소 cost는 6 입니다. 따라서, 기존의 cost 9 짜리 1 -> 5 경로는 폐기되고 6으로 새로 업데이트 됩니다.

*다익스트라 알고리즘은 모든 cost가 음의 정수가 아니어야만 동작 가능합니다. 음의 정수가 포함되어 있을 경우, 최단거리를 구하는 알고리즘은 Bellman-Ford 알고리즘으로 향후 포스팅 하도록 하겠습니다.

*시간복잡도는 우선순위 큐를 사용할 경우, O($ElogV$)입니다.

3. 코드구현

• 노드에 대한 정보를 담을 때는, graph를 활용합니다.
• 우선순위 큐와 거리 정보를 담을 list를 사용합니다.
• 반복문을 통해, 출발 노드 부터 최소거리 순으로 거리 정보를 업데이트 해줍니다.
• 위 그림의 1 -> 2 -> 5와 같이 거쳐서 가는 경로에 대한 거리 정보도 업데이트 해줍니다.
• 거리정보 업데이트가 완료되면, 수행을 종료합니다.

코드는 백준 알고리즘 1753번 문제 풀이를 통해 작성하였습니다.(https://www.acmicpc.net/problem/1753)

import sys
import heapq

INF = 1E10

v, e = map(int, sys.stdin.readline().split())
k = int(input())

graph = [[]for _ in range(v+1)]
heap_q = [(0, k)]
distance = [INF] * (v+1)
distance[k] = 0

for _ in range(e):
    start, end, cost = map(int, sys.stdin.readline().split())
    graph[start].append((cost,end))


def dijkstra():
    while heap_q:
        nowCost, node = heapq.heappop(heap_q)

        if distance[node] < nowCost:    # if distance is updated
            continue

        for newCost, newNode in graph[node]:    # check adjacent node
            dist = distance[node] + newCost
            if distance[newNode] > dist:    # update lower cost
                distance[newNode] = dist
                heapq.heappush(heap_q, (dist, newNode))

dijkstra()

for i in range(1,v+1):
    if distance[i] == INF:
        print('INF')
    else:
        print(distance[i])

Reference

https://jaemunbro.medium.com/algorithm-%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-with-python-20f061fdc8f1