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

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

다익스트라 알고리즘은 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다.

한 정점에서 연결된 정점을 방문하면서 비용을 계산하여 최단 거리를 갱신해주며 탐색하는 방식이다.

 

분류

그리디 알고리즘(Greedy Algorithm)

 

구현방식

인접행렬

다익스트라 본인이 제안한 방법으로

 

1 )정점 개수만큼의 최단 거리 배열을 만들고 모든 최단거리 초기값을 무한대로 설정한다.

2) 시작 정점의 거리값을 0으로 놓는다.

3) 미 방문 정점들 중 최단 거리 정점을 선택한다. (이 과정에서 선형 탐색이 필요하다)

4) 현재 정점과 연결된 미 방문 정점들을 확인하여 최단거리를 업데이트해준다.

 

무한 순환 방지를 위해 방문체크를 할 필요가 있다.

 

시간 복잡도는 O(N²)이다.

 

우선순위 큐

기존의 다익스트라 알고리즘을 개선한 방법으로

 

1) 기존과 동일

2) 기존과 동일

3) 우선순위 큐를 만들고 시작 정점을 넣는다.

4) 현재 정점에서 시작정점까지 경로길이가 짧을수록 높은 우선순위를 준고 우선순위 큐에 넣는다.

5) 현재 정점으로부터 미 방문 정점을 모두 방문한다.

 

무한 순환 방지를 위해 방문체크를 할 필요가 있다.

 

시간 복잡도는 O(NlogN)이다.

 

예시

아래 그래프에서 1번 노드에서 시작해 6번노드로 가는 최단 거리를 구해보자

시작 노드의 거리를 0으로 두고 방문체크를 한다.

1번 노드와 연결된 노드들까지의 거리를 업데이트 해준다.

다음으로 방문하지 않았고 가장 최단거리인 노드를 방문한다.

위 그래프에선 2번노드를 방문하게된다.

마찬가지로 연결된 노드들의 거리를 업데이트한다.

(1번->2번 까지의거리 + 2번->n번 까지의 거리)

위 과정을 반복한다.

3번노드에 방문했을 경우 4번, 6번 노드까지의 거리가 더 짧아졌으므로 갱신해준다.

그리고 다시 반복한다.

4번노드에선 갱신된 값이 없으므로 넘어간다.

5번 노드에서는 6번노드까지의 거리가 갱신된다.

모든 노드에 방문한 것이 확인이 되면 탐색을 종료하고 목표 노드의 거리 값을 반환해주면 된다.

 

조건

간선의 값(비용)이 양수일 때만 가능하다.

 

현실에선 경로가 음수가 될 가능성이 없기때문에 실생활에서 많이 사용되는 알고리즘이다.