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

그래프의 가중치가 없거나, 모든 간선의 가중치가 동일하다면 BFS를 이용하여 최단거리를 구할 수 있다.

왜 쓰는가?

그런데 가중치가 다를 경우, BFS를 이용하여 최단거리를 구하는 데에 어려움이 있다.

이를 해결하기 위해 나온 알고리즘 중 하나가 다익스트라 알고리즘

 

언제 쓰는가?

어떤 점에서 다른 모든점으로 가는 최단거리를 구할 때

1~5까지의 점이 있고, 1에서 출발한다고 가정. 1-2의 최단거리, 1-3의 최단거리, 1-4의 최단거리, 1-5의 최단거리를 구할 수 있다는 의미

 

어떻게 쓰는가?

기본 개념

어떤 정점에서 시작해서 각 정점으로 가는 최단 거리를 구해야 한다.

 

dist를 저장할 자료구조를 선택하고 시작 정점을 0, 나머지 정점을 inf로 초기화한다.

(3번에서 시작한다고 가정했을 때, 3번으로 가는 최단거리는 0이기 때문)

 

최소값(맨 처음에는 0으로 저장한 시작 정점이 선택됨)을 선택하고, 해당 정점과 이어진 정점까지의 거리를 갱신한다.

(처음에는 "inf→시작점에서 해당 점으로의 가중치"로 초기화될 것)

 

해당 정점을 다시 방문하지 않도록 visited 배열과 같은 조치 필요

 

dist에 저장된 값 중 최소 값을 선택하고, 거리 갱신, 방문 체크 반복

 

모든 정점을 다 방문하면 어떤 점으로부터 다른 점으로의 최단거리를 알 수 있다.

 

시간 복잡도 $O(V^2)$

$V^2$ 알고리즘에서는 2차원 배열(인접 행렬)을 사용한다. for문을 이용해 최솟값을 찾는 방법. 해당 방법은 정점의 수가 작을 때 유용하다.

(인접 행렬: 두 정점 i, j가 연결관계에 있을 때 graph[i][j]값을 1로, 그렇지 않다면 graph[i][j] 값을 0으로 표현)

 

최소값을 찾는 데에 $O(V^2)$이 소요되기 때문에 시간 복잡도는 $O(V^2)$

 

C++ 코드는 아래 페이지 참고

https://im-your-supporter.tistory.com/191

[코드트리] 각 정점까지의 최단 경로3 C++

 

시간 복잡도 $O(ElogV)$

거리 배열(dist) 내의 값들 중 최솟값을 반복적으로 골라주어야 하기 때문에 우선순위큐를 이용.

 

O(V): Q에 V개가 들어있으므로 while(!pq.empty()) 총 V번 반복.

O(VlogV)-최소값 찾기+제거: [최소값 찾기] 우선순위 큐를 통해 관리가 되므로 가장 앞에있는 값을 가져오면 된다(O(1)). [최소값 제거] 최소값을 제거한 후 인덱스를 당기는? 과정이 O(logV)가 소요되므로 총 O(VlogV)

O(ElogV)-인접 노드 검사: 최소값으로 뽑은 노드의 인접노드를 검사. 이 부분은 모든 간선에 대해 한 번씩만 돌기 때문에 E(간선의 수)번 반복됨. 모든 간선을 보며 dist 갱신. 우선순위 큐의 값 갱신 O(logV). 모든 간선에 대해 O(logV)가 진행되기 때문에 O(ElogV)가 된다.

일반적인 경우 E>=V이기 때문에 총 시간 복잡도는 O(ElogV)

 

C++ 코드는 아래 페이지 참고

https://im-your-supporter.tistory.com/192

[코드트리] 각 정점까지의 최단 경로 C++

 

 

한계

음수 가중치가 있는 그래프에서는 다익스트라를 사용할 수 없다(바르게 작동하지 않을 수 있음).

음수 가중치가 있으면 다시 골랐을 때 정점에 도달하는 dist 값이 더 작아질 수도 있기 때문에 최단거리임을 보장할 수 없게 됨.

 

해결

벨만-포드 알고리즘을 이용하면 음수 가중치가 있는 그래프의 최단거리를 구할 수 있다.