다익스트라 알고리즘(Dijkstra's Algorithm)

다익스트라란? 

 컴퓨터 과학자 에드거 데이크스트라에 의해 만들어진 그래프에서 노드 사이의 최단 경로를 찾는 알고리즘이다.

---

 

즉, 다익스트라 알고리즘은 주어진 그래프에서 시작점으로부터 원하는 노드로 가기에 가장 적은 비용을 갖고 도착하는 경우를 찾는다. (최단거리,최소비용) 

위에서 말한 알고리즘을 적용하는 그래프는 방향이 주어지거나 안주어진 그래프의 경우로, 

둘다 사용할 수 있지만 가장 많이 사용되는건 방향을 가진 그래프안에서 사용된다. 

---

 

그럼 다익스트라 알고리즘은 어떻게 작동할까? 

그리디처럼 현재 주어진 노드에서 가장 적은 비용으로 갈 수 있는 노드로 움직이는 방식을 가졌다.

 상세한 설명 이전에 아래 그림을 보자 

 

 

우리가 가고자하는 노드로 도착하기전에 이전에 방문한 곳을 계속해서 돌다간 도착할 수 없다. 

그렇기에 모든 노드를 일단 무제한의 큰 수를 두고, 비교하며 가장 적은 비용으로 갱신한다

(비교가 조건이 되어 BASECASE로 작용할 수 있다) 

작동방식은 이러하다.

 

1 시작노드에서 인접한 노드들 중 가장 적은 비용이 드는 노드의 방문기록을 비교하여 수정(축적)한다.

2. 이후 가장 적은 비용이 들었던 노드 순으로 위에 1과 같이 반복하며 queue를 사용해 BFS식으로 넓게 움직인다

3. 도착하고자하는 노드의 방문기록에 최소 비용이 적재된다. (이미 최소 비용으로 적재되더라도 queue에 담아있는 녀석들이 움직일테지만 위에서 조건으로둔 BASECASE를 통해 필요없는 행동들은 금방 멈춘다) 

---

 

이렇게 움직였을 떄 다익스트라 알고리즘의 시간복잡도의 경우

정점 개수가 V, 간선 개수가 E일 때 기본적인 최적화를 거치면 O(ElogV)의 시간복잡도를 가진다. 

 

어떻게 작동하는지 설명헀지만 우리는 개발자이기때문에 코드를 통해 다시 이해해보자. 

 

---

1753번: 최단경로

 

import sys
import heapq

INF = float('inf')
V, E = map(int, sys.stdin.readline().split())
K = int(sys.stdin.readline())
graph = [[] for _ in range(V + 1)]
answer = [INF] * (V + 1)
queue = []

for i in range(E):
    u, v, w = map(int, sys.stdin.readline().split())
    graph[u].append([v, w])

def dijkstra(start):
    answer[start] = 0 
    heapq.heappush(queue, [0, start]) 

    while queue:
        current_w, current_node = heapq.heappop(queue)

        if answer[current_node] < current_w:
            continue

        for next_node, weight in graph[current_node]:
            next_w = current_w + weight
            if next_w < answer[next_node]:
                answer[next_node] = next_w
                heapq.heappush(queue, [next_w, next_node])

dijkstra(K)
for i in answer[1:]:
    print(i if i != INF else "INF")