그래프 - 최단거리 알고리즘 1 다익스트라 알고리즘

다익스트라 알고리즘이란

다익스트라 알고리즘은 그래프의 정점들 사이에 가중치가 주어졌을 때 한 정점에서 다른 정점으로 가는 최단 경로를 구하는 알고리즘이다.

다익스트라를 비롯한 대부분의 최단 거리 알고리즘은 음수 가중치를 갖는 간선이 있는 경우 음수 싸이클을 돌면서 가중치의 총합을 발산하는 경로가 생길 수 있어서 최단 거리를 계산할 수 없다.

다익스트라 알고리즘의 구현

다익스트라 알고리즘은 BFS와 우선순위 큐를 이용한다. 우선순위 큐에는 정점과 그 정점까지 가는 현재까지의 최단 경로를 한 쌍으로 해서 넣는다. BFS를 통해 정점을 하나씩 방문하면서 우선순위 큐에서 현재 방문하지 않은 정점으로 가는 최단 경로를 하나씩 꺼내면서 스패닝 트리를 만들면, 각 정점으로 가는 최단 경로를 구할 수 있다.

다익스트라 알고리즘의 시간 복잡도는 매 간선을 한번 씩 확인하는 데 E, 우선순위 큐에 들어갈 수 있는 최대 개수인 간선의 수 E에 우선순위 큐를 연산하는 데 필요한 logE를 곱한 logE*E, 따라서 총 ElogE의 시간 복잡도를 갖는다.