Dijkstra Algorithm

• 시작 정점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘
• 음수 가중치가 없는 그래프에서만 사용할 수 있음
• Greedy 알고리즘의 일종으로, 항상 현재 알고 있는 가장 짧은 경로를 선택

알고리즘의 동작 과정:

1. 시작 정점의 거리를 0으로, 나머지 정점들의 거리를 무한대로 초기화
2. 방문하지 않은 정점 중 최단 거리가 가장 짧은 정점을 선택
3. 선택한 정점과 인접한 정점들의 거리를 갱신 (거리와 거리를 비교해서 더 작은 지점으로 갱신하는 것을 완화(Relaxation)라고 함)
4. 모든 정점을 방문할 때까지 2-3단계를 반복

다익스트라 알고리즘의 특징

• 음수 가중치가 없는 그래프에서만 사용 가능

  • 음수 간선이 존재하면 다익스트라를 사용할 수 없다. 다익스트라의 가정은 한번 방문한 정점은 최단 거리가 확정된다"는 것인데, 음수 가중치가 있으면 이 가정이 깨지기 때문

  • 만약, 음수를 없애고 다익스트라를 사용한다면? (음수의 최댓값이 -100일때, 모든 간선에 100을 더해서 양수로 만든 다음 다익스트라 수행)

  • ⇒ 그래도 불가, 최단 거리의 경로가 바뀔 수 있음. 간선의 개수가 다르기 때문임

    왜 음의 간선이 있을 때 다익스트라 알고리즘을 사용하지 못하는가

  • 또한, 음수 사이클이 존재한다면 다익스트라를 사용할 수 없다.

    • 음수 사이클이 존재하면 최단 거리 자체가 정의되지 않는다. 사이클을 돌면 돌수록 경로의 길이가 무한히 감소하기 때문이다.

구현

• Prim’s algorithm은 priority_queue에서 한 정점을 꺼내고, 해당 정점이 방문하지 않았을 때, 해당 정점을 방문 처리와 함께 MST에 추가하고 다음 정점을 탐색했다.
• Dijkstra algorithm은 priority_queue에서 한 정점을 꺼내고, 해당 정점까지의 거리가 현재 알고 있는 최단 거리일 때, 인접 정점들의 최단 거리를 갱신한다.

시간복잡도 : $O(ElogV)$