[알고리즘] 다익스트라 알고리즘

 

Goal
- 다익스트라 알고리즘을 이해하고 활용할 수 있다. ✔
- 다익스트라 알고리즘을 구현할 수 있다. ✔

 

다익스트라 알고리즘

---

 

그래프 탐색 문제와 유사하나 정점 간의 간선에 가중치가 있어 경로 상의 가중치를 모두 더했을 때 가장 최소가 되는 경로를 구하는 문제이다.

 

그냥 그래프 탐색으로 모든 경로를 탐색하여 최솟값을 구할 수 있으나, 보통 시간 초과 오류가 난다.

 

다이나믹 프로그래밍을 사용해 그래프 탐색을 최대한 최소화 하는 것이 이 알고리즘의 기본 아이디어이다.

 

간단하게는 그래프 탐색과 다이나믹 프로그래밍을 함께 활용하는 것이라고 이해하면 좋다.

 

 

다익스트라 알고리즘의 원리

---

탐색을 시작할 점을 잡는다. (거리의 합이 중요하므로 시작점은 하나만 잡을 수 있다.)

 

해당 그래프 주위의 간선들을 탐색하여 그래프를 탐색해나간다

(여기까진 그냥 그래프 탐색과 똑같다.)

이때, 조건이 더 붙는다.

• 방문한 노드가 처음 방문이라면 해당 노드까지의 거리(가중치의 합)를 갱신하고 해당 노드도 탐색한다.
• 처음이 아니라면 이미 갱신되어있는 거리와 비교하여 거리가 더 작을 때만 해당 노드를 탐색한다. (DP를 이용한탐색의 최소화)

BFS와 비슷한 방식으로 탐색하는데 이때 중요한 점은 BFS는 탐색의 순서가 없지만, 다익스트라의 경우 가중치가 더 적은 간선이 더 최단거리일 확률이 높으므로 지금까지 거리가 가장 작은 노드부터 탐색한다.

 

이때, 보통 heapq를 사용하여 탐색한다.

 

즉, bfs인데 Heapq와 DP가 활용된 BFS라고 할 수 있겠다.

 

구현

---

그래프 탐색을 이미 이해하고 있다면 사실 원리보다 구현을 보고 이해하는 것이 더 빠를 수 있다.

https://www.acmicpc.net/problem/1753

1753번: 최단경로

백준의 다익스트라 알고리즘을 연습하는 문제이다.

 

코드

 

import sys
import heapq

input = sys.stdin.readline
INF = sys.maxsize
V, E = map(int, input().split())
K = int(input())
dp = [INF]*(V+1)
heap = []
graph = [[] for _ in range(V + 1)]

def Dijkstra(start):
    dp[start] = 0
    heapq.heappush(heap,(0,start))
    while heap:
        wei,now = heapq.heappop(heap)
        
        for w,next in graph[now]:
            weight = w + wei
            if dp[next] > weight:
                dp[next] = weight
                heapq.heappush(heap,(weight,next))


for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u].append((w, v))


Dijkstra(K)
for i in range(1,V+1):
    print("INF" if dp[i] == INF else dp[i])

 

코드를 보면 알겠지만, BFS와 비슷한데 큐 대신 우선순위 큐를 사용하고, 우선 순위 큐에서는 최단 거리부터 탐색하게끔 하여 더 시간이 많이 걸리는 탐색은 if문에서 걸려서 더 이상 탐색하지 않게끔 한다.

 

이때 사이클이 있다면 dp에 존재하는 값이 사이클을 돈 값보다 무조건 더 작을 것이므로 사이클은 돌지 않게 된다.

 

이러한 관점에서 거리에 -값이 있다면 다익스트라 알고리즘이 아니라 밸만 포드 알고리즘을 사용하여야한다✅ 

 

결국 포인트는 어떤 한 점으로부터 다른 점들로까지 가능한 최단 경로를 알려주는 다익스트라 알고리즘은 BFS와 DP를 혼합한 형태라도 봐도 좋다는 것이다. ✅