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

이번에는 다익스트라 알고리즘에 대해서 공부를 해보았다.

 

다익스트라 알고리즘은 단일 시작점으로부터 다른 노드들까지의 최단 경로를 구하는 알고리즘이다.

또한, 음의 가중치를 허용하지 않는 최단경로를 말한다.

다익스트라 그림

위의 그림을 설명하자면,

시작점을 제외한 모든 저점과 시작점 사이의 거리를 무한으로 표현하고 다음과 같은 수행을 반복한다.

1. 현재 선택한 정점(처음엔 시작점)에 곧장 연결되고, 아직 방문하지 않은 정점들을 모두 본다.

2. 선택한 정점과 보고있는 정점 사이의 거리와 시작 정점과 선택한 정점까지의 최단거리의 합이 현재까지 구한 시작 정점과 보고 있는 정점 사이의 거리보다 짧을 경우, 이를 갱신해준다.

3. 1, 2번 수행이 모두 끝난 이후, 아직 방문하지 않은 정점들 중 시작점과의 거리가 가장 짧은 정점을 선택한다.

4. 방문하지 않은 정점이 존재하여 정점을 선택했다면, 현재 구한 시작점으로부터의 현재 선택한 정점 사이의 거리는 최단거리이다.

5. 방문하지 않은 정점이 존재하지 않는다면, 수행을 종료한다. 그렇지 않으면 1번으로 돌아가 수행을 반복한다.

                                                                                         출처: https://cloge.tistory.com/26 [cloge 이야기]

다익스트라 알고리즘의 시간 복잡도

V: 노드의 숫자, E: 간선의 숫자이다.

기본 알고리즘의 시간복잡도는 O(V^2)이다.

 

우선순위 큐를 사용해서 이를 좀 더 개선 할 수 있다.

방법은 2가지인데, 1번째로는 각 정점마다 인접한 간선들을 모두 검사하는 작업이고, 2번째로는 우선순위 큐에 원소를 넣고 삭제하는 작업이다.

 

모든 간선이 한번씩 검사된다는 점에서 첫 번째 작업이 O(E), 각 간선마다 우선수위 큐에 자료가 삽입 연산이 일어난다는 점에서 O(ElogE)이며, 이 둘을 합쳤을 때, (E+ElogE)의 시간복잡도는 O(ElogE)가 된다.

 

대개의 그래프의 경우 V^2 > E이므로 O(logE) = (logV)이고, 따라서, 시간 복잡도는 O(ElogV)가 될 수 있다.

 

맨처음 시작할 때 음의 가중치를 허용하지 않는다고 하였는데, 다익스트라는 음수 가중치가 존재하지 않는 가정안에서만 그리디 알고리즘의 관점으로 최단 경로를 구할 수 있다.

                                                                                  출처 : https://blog.naver.com/qbxlvnf11/221377612306

음의 가중치를 가진 간선이 있다면 '벨만-포드 알고리즘'을 사용해야한다. 추후에 올릴 생각이다.