[알고리즘] 다익스트라(Dijkstra)

다익스트라(Dijkstra)

출발점에서 모든 점으로 가는 최소거리를 각각 구하고 싶을 때 사용한다.

음수 가중치는 사용이 불가능하다.

음수 가중치가 없기 때문에 최단 경로가 확정된 정점들과 연결된 정점 중 출발점에서 가장 거리가 짧은 정점은 최단거리임을 확장할 수 있다.

거리가 3인 정점이, 3보다 더 긴 경로를 타고 더 빠르게 갈 수 없는 것처럼 말이다.

알고리즘

1. 출발점으로부터 가장 거리가 짧은 정점 X를 구한다.

2. 정점 X까지의 거리를 정점 X의 최단 거리로 확정한다.

3. 정점 X를 경유하는 경로와 비교해, 연결된 정점들의 거리를 갱신한다.

4. 1~3을 반복한다.

시간 복잡도

1번 과정을 선형 탐색을 이용하게 되면 O(V^2), V는 노드의 개수

-> 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 거리 테이블의 길이(=노드의 개수)만큼 순차탐색을 수행하기 때문

 

Priority Queue와 같은 이진 힙을 이용하게 되면 O((V+E)logV), E는 간선의 개수

-> 우선순위 큐에서 꺼낸 노드를 탐색할 때 해당 노드와 연결된 노드들만 탐색하므로 최악의 경우라도 총 간선의 개수인 E만큼 반복

구현

3번의 과정을 진행함에 있어서 priority queue 내부의 값을 바꾸는 것은 매우 어렵다.

pair를 통해 (거리, 정점) 쌍을 힙에 보관하고 현재 정점 최단거리도 dist 배열에 따로 보관하여 이를 확인한 뒤 최단 거리임을 확정하자.

 

dist배열: 시작점으로부터의 거리

- 처음에는 INF로 초기화

- dist[시작점]은 0

C++

※ Priority Queue ※

Queue와 똑같이 사용하는데, 내림차순으로 자료가 정렬되어 있다.

.top()을 하면 priority queue에서 가장 큰 값이 나온다.

priority_queue <pair <int, int> > pq;

pair가 안에 들어가면 첫번째 값을 기준으로 정렬한다.

pair의 앞에는 거리, 뒤에는 정점을 넣어준다.

가장 작은 값을 얻기 위해서는 push 할 때 -1을 곱하여 넣어주면 된다.

void dijkstra(int num)
{
	priority_queue <pair <int,int> > pq;
	pq.push(make_pair(0, num));
	dist[num]=0;
	while (!pq.empty()){
		 int now = pq.top().second;
		 int nowdist = -pq.top().first;	
		 pq.pop();
		for (pair< int, int> next : adj[now]){
			if (dist[next.first] >= nowdist + next.second){
		    	dist[next.first] = nowdist + next.second;
		    	pq.push(make_pair(-dist[next.first], next.first));
			}
		}
	}	
}

Python

정점 num까지의 최단거리 구하기

dist: 정점 num까지의 최단거리 list

N: 총 정점의 개수

node: adjacent list [(인접 node, 인접 node까지의 거리)]

num정점에서 num정점까지의 거리는 0으로 최단거리이기 때문에 heap에 (0, num)을 push하면서 시작

from heapq import *
import math

def dijkstra(num):
  dist = [math.inf for i in range(N)]

   pq = []
   heappush(pq, (0, num))
   while pq:
        nowdist, now = heappop(pq)
        # heap에서 뽑아낸 거리가 이미 갱신된 거리보다 클 경우(=방문한 셈) 무시
        if dist[now] < nowdist:
            continue
        for next_node in node[now]:
            if dist[next_node[0]] > nowdist + next_node[1]:
                dist[next_node[0]] = nowdist + next_node[1]
                heappush(pq, (dist[next_node[0]], next_node[0]))

정리

출발점 하나 - 모든 도착점, 음수 가중치 NO, 대신 빠름

1. 시작 정점이 정해져 있을 때 다른 모든 정점으로의 최단거리를 구한다

2. 모든 간선들의 가중치가 양수여야 한다

    -> 다익스트라는 거리가 한 번 확정되면 그 노드에 대해선 다시 계산을 안 하는데 음수 가중치가 있으면 바뀔 수 있기 때문에

3. 시간 복잡도 : O((V+E)logV)

 

참고:
- 우선순위 큐를 활용한 개선된 다익스트라 알고리즘
- 최단경로를 위한 다익스트라 알고리즘