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

0. 개요

다익스트라 알고리즘은,

특정 시작 점에서 다른 한점까지의 최단거리를 측정할 수 있다.

단, 모든 간선은 양의 간선 이여야 한다.

하는데 사용하는 알고리즘이다.

먼저 개념은 아래의 EBS 영상이 가장 잘 나타내고 있음으로 아래의 영상을 참고하길 바란다.

 

1. 구현 방법

사용되는 자료구조는 힙큐 혹은 우선순위 큐 이다.

1. 우선 그래프에 있는 모든 정점들에 대해서 거리를 메모할 리스트를 생성한다.

dist = [INF for _ in range(V)]
# INF는 엄청 큰 수 / V는 꼭지점의 개수

2. 시작점을 우선순위 큐에 넣는다.

이 때, 거리가 가까운 정점을 먼저 방문해야 하므로 (거리, 정점 번호) 로 우선순위에 넣는다.

3. 우선순위 큐에서 정점 하나를 꺼내서 인접한 꼭지점의 dist에 거리를 최신화 한다.

[ 우선순위 큐에서 꺼낸 정점 = A  |  A와 인접한 정점 = B | A와 B의 가중치를 W라 하면,

dist[B] > dist[A] + W  를 만족한다면 최신화 해야한다. ]

거리가 최신화 되었다면, 인접한 정점의 dist 거리와 정점번호를 우선순위 큐에 삽입 한다.

4. 큐가 반복될 때까지 3번을 반복한다.

2. 코드

def Dijkstra(graph, start, V):
	dist = [INF for _ in range(V + 1)]
	que = PriorityQueue()
	que.put((0, start))
	
	while not que.empty():
		W, E = que.get()
		
		for weight, num in graph[E]:
			if dist[num] > weight + dist[E]:
				dist[num] = weight + dist[E]
				que.put((dist[num], num))

3. 시간 복잡도

정점의 개수를 E라고 할 때

- 각 정점을 1번씩 방문하게 되고 인접한 간선을 검사하므로 O(E)

- 우선순위 큐에 들어갈 수 있는 최대 개수는 E, 우선순위 큐에서 insert & pop 을 진행하는데 O(logE)

그러므로 O(ElogE) 의 복잡도를 가진다.