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

다익스트라 알고리즘이란?

대표적인 그리디 알고리즘 중 하나로 항상 노드 주변의 최단 경로만을 택하는 알고리즘이다. 이 때, 주로 BFS를 사용한다

방법

1. 시작 노드에서 갈 수 있는 노드의 비용을 적고, 갈 수 없는 노드의 비용을 무한대로 채운다.
2. 노드의 비용 중, 가장 비용이 적은 노드를 선택(여기서 우선순위큐 적용 가능)하고 시작노드에서 그 노드를 들려 다른 노드로 간 경우 거리를 계산한다. 계산한 거리 중, 시작노드에서 바로 간 경우보다 비용이 적게 든다면 적게 든 비용으로 그래프를 채운다.
3. 2번을 반복한다.
4. 목적지에 도착하면 return

시간 복잡도

• 순수?한 다익스트라 알고리즘은 시간 복잡도가 O(V^2)이다.
• BFS에서 가장 가까운 노드를 찾을 때, 우선순위큐를 적용하면 시간 목잡도가 O((V+E)logV)로 줄어든다. 이 때, 모든 정점이 출발지에서 도달이 가능하다면 최종적으로 O(ElogV)가 된다.

한계와 해결방법

• 가중치가 음수인 경우는 처리할 수가 없다.
  • 어느 노드에서 다음 노드에 도착했을 때, 다익스트라 알고리즘은 그 노드에 대해 더이상 최신화를 시키지 않기 때문에 이후 음수로 인해 최단 경로가 뒤바뀔 때, 오류가 발생하기 때문이다.
  • 이런 경우, 특정 값을 모든 경로에 더해서 양수로 변환하거나, 벨만-포드 알고리즘을 사용하는 것을 고민해봐야 한다.