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

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

한 정점에서 다른 정점으로 가는 최단거리를 구하는 알고리즘으로 가중치가 음수면 사용이 불가능하다.

다익스트라는 최단거리는 최단거리들로 이루어져 있다는 Greedy한 아이디어로 만들어진 알고리즘이다.

주로 우선순위 큐와 BFS를 이용하여 구현되며, 작동 방식은 다음과 같다.

1. 아직 방문하지 않은 정점들 중 거리가 가장 짧은 정점을 하나 선택해 방문한다.

2. 해당 정점에서 인접하고 아직 방문하지 않은 정점들의 거리를 갱신한다.

* 작동 예시

0번 정점에서 시작한다고 가정하고, 위와 같은 그래프가 있을 때 작동방식은 다음과 같다.

작동 방식	방문한 정점	PrioirityQueue	사용가능한 간선
1. 0번 정점에서 가까운 간선 중 최소 가중치를 가진 0-1 간선을 선택한다.	0	[7, 9, 14]	0-1, 0-2, 0-3
2. 0번 정점과 1번 정점에서 가중치가 작은 간선을 선택한다.  (단, 1번정점에서 선택하는 경우는 0-1 간선의 가중치인 7을 더해야 한다.)	1	[9,  14, 10+7, 15+7]	0-2, 0-5, 0-1-2, 0-1-3
3. 0,1,2 정점에서 사이클을 만들지 않는 간선 중 가중치가 작은 간선을 선택한다.	2	[9+2, 14, 9+11, 7+15]	0-2-5, 0-5, 0-2-3, 0-1-3
4. 0,1,2,5 정점에서 사이클을 만들지 않는 간선 중 가중치가 작은 간선을 선택한다.	5	[9+11, 9+2+9, 7+15]	0-2-3, 0-2-5-4, 0-1-3
5. 0,1,2,3,5 정점에서 사이클을 만들지 않는 간선 중 가중치가 작은 간선을 선택한다.	3	[9+2+9, 9+11,6]	0-2-5-4, 0-2-3-4
6. 0,1,2,3,5 정점에서 사이클을 만들지 않는 간선 중 가중치가 작은 간선을 선택한다.	4

위 순서를 통해 정점과 정점사이의 최단 거리를 구한다.

핵심은 최단거리는 최단거리들로 이루어져 있다는 생각이고, 선택한 정점과 인접한 최소한의 가중치를 가진 간선을 선택하는 것은 프림 알고리즘과 비슷하다.

하지만, 프림 알고리즘과 달리 우선순위 큐에 해당 가중치를 계속 더해가며 최단 경로를 찾는 알고리즘이다.

백준/1753 :: 최단경로 문제

백준/1753 :: 최단경로 풀이