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

오늘 포스팅할 내용은 다익스트라 알고리즘으로 앞서 포스팅했던 벨먼-포드 알고리즘과 마찬가지로 그래프의 최단 경로를 구하는 알고리즘 이다.

 

알고리즘의 이름은 개발자 에츠허르 W, 데이크스트라[Edsger W. Dijkstra]의 이름에서 유래했다.

 

다익스트라 알고리즘을 보기전에 그래프 자료구조와 벨먼-포드 알고리즘을 보고 오면 더 이해하기 쉬울 것이다.

[자료구조] 그래프 (Graph)

[알고리즘] 벨먼-포드 알고리즘 (Bellman-Ford Algorithm)

 

현재 차근차근 해보자는 생각에 기초 공부를 하는 중이다. 좀 더 자세한 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 작성해 보겠다. 

틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다!

---

📝 개념

다익스트라 알고리즘은 그래프의 최단 경로를 구하는 알고리즘이다.

시작점에서 끝점에 이르는 경로 중에서 간선 비용의 합이 최소인 것을 찾는다.

다익스트라 알고리즘

여기서는 정점 A를 시작점, 정점 G를 끝점으로 다익스트라 알고리즘을 설명해 보겠다.

 

다익스트라 알고리즘

먼저 각 정점 비용의 초깃값을 설정한다. 시작점은 0, 그 외 정점은 무한대(∞)로 설정한다.

해당 비용은 최단 경로의 잠정적 비용을 나타낸다.

 

다익스트라 알고리즘

시작점에서 출발하며, 하늘색으로 표시하였다.

 

다익스트라 알고리즘

현재 정점에서 도달할 수 있고 아직 탐색하지 않은 정점을 찾는다. 발견한 정점은 다음에 탐색할 후보가 된다. 후보는 핑크색으로 표시하겠다. 이 경우에는 B와 C가 후보가 된다.

 

다익스트라 알고리즘

후보의 정점의 비용을 각각 계산한다. 계산 방법은 '현재 있는 정점의 비용 + 현재 있는 정점에서 후보 정점에 도달하는 간선의 비용'이다. 예를 들어 위같은 경우 시작점 A의 비용은 0이므로 B의 비용은 0 + 2 = 2 가 된다. 마찬가지로 C는 0 + 5 = 5 가 된다.

 

다익스트라 알고리즘

계산 결과가 현재 비용보다 작으면 갱신 한다. 정점 B와 C의 현재 비용은 무한대이고 계산한 결과는 무한대 보다 더 작은 2와 5이기 때문에, 각각 2와 5로 값을 갱신해 준다.

 

다익스트라 알고리즘

후보 정점 중에서 비용이 제일 작은 정점을 선택한다. 여기선 2 < 5 이기 때문에 정점 B가 선택 된다.

이 시점에서는 A-B가 시작점에서 정점 B에 도달하는 최단 경로이다. 왜냐하면 다른 경로는 반드시 정점 C를 경유해야 하므로 현재 경로보다 비용이 더 많이 들기 때문이다.

 

다익스트라 알고리즘

최단 경로로 결정된 정점 B로 이동한다.

 

다익스트라 알고리즘

현재 위치에서 도달할 수 있는 정점을 새롭게 후보로 추가한다. 여기서는 D, E가 추가되어 전체 후보는 C, D, E가 된다.

 

다익스트라 알고리즘

동일한 방법으로 각 후보 정점의 비용을 계산한다. 정점 B를 거쳐 정점 C로 가는 비용은 2 + 6 = 8이다.

하지만 현재 C의 비용인 5가 더 작기 때문에 갱신하지 않는다.

 

다익스트라 알고리즘

나머지 정점 D와 E의 비용은 2 + 1 = 3. 2 + 3 = 5로 무한대 보다 작기때문에 갱신해 준다.

 

다익스트라 알고리즘

남은 후보 정점 중에서 비용이 제일 작은 정점을 선택한다. 여기서는 비용이 3인 정점 D가 가장 적은 비용이 든다.

이 시점에서 선택한 정점 D로 가는 경로는 A-B-D가 시작점 부터 정점 D까지 가는 최단 경로가 된다.

 

경로 A-B-D는 후보 정점 중 가장 비용이 적은 것을 선택하여 얻은 경로이다. 따라서 다른 정점을 경유하여 D로 이동하면 반드시 지금보다 비용이 더 커진다.

 

이처럼 다익스트라 알고리즘은 각 정점으로 가는 최단 경로를 하나씩 결정해 나가면서 그래프를 탐색한다.

 

다익스트라 알고리즘

종점 G에 도착할 때까지 동일한 작업을 반복한다.

D로 이동하여 E의 비용을 계산하지만 3 + 4 = 7 이기 때문에 5 < 7 로 갱신 되지 않는다.

현재 후보는 C와 E인데, 둘 다 같은 값 5이므로 어떤 것을 선택해도 무방하다.

 

다익스트라 알고리즘

여기선 먼저 후보가 된 C를 선택하겠다. 이에 따라 C로 가는 최단 경로가 결정된다.

 

다익스트라 알고리즘

C로 이동한다. 이번엔 F가 새로운 후보에 되고, F의 비용은 13으로 갱신된다. 이제 후보는 E의 5와 F의 13이 된다.

 

다익스트라 알고리즘

둘 중 더 작은 E가 선택되어 E로 가는 최단 경로가 정해진다.

 

다익스트라 알고리즘

E로 이동한다. G가 새로운 후보가 되고, G의 이동 비용은 14로 갱신된다. 후보는 F의 13과 G의 14이고, 더 작은 F가 선택되어 F로 가는 최단 경로가 결정된다.

 

다익스트라 알고리즘

F로 이동한다. G의 값을 계산하면 13 + 7 = 20이지만, 현재 값인 14가 더 작기 때문에 G의 비용은 갱신되지 않는다. 후보는 비용이 14인 G 뿐이므로 G가 선택되어 G로가는 최단 경로가 결정된다.

 

다익스트라 알고리즘

원하던 종점 G의 최단 경로에 도달했으므로 탐색을 종료한다.

최종적으로 만들어진 살구색 트리를 최단 경로 트리라고 하며, 각 정점으로 이동하는 최단 경로를 나타낸다.

 

다익스트라 알고리즘

여기서 빨간색 선으로 표시된 경로가 시작점 A에서 끝점 G로 가는 최단 경로가 된다.

 

여기까지가 다익스트라 알고리즘 탐색 방법 이었다.

---

✔️ 추가 내용

벨먼-포드 알고리즘

다익스트라 알고리즘도 벨먼-포드 알고리즘과 마찬가지로, 방향성 그래프에서도 최단 경로를 찾을 수 있다.

단, 음수의 비용을 포함하는 그래프에서는 올바른 최단 경로를 찾지 못할 수 있다. 이것이 벨먼-포드 알고리즘과 다른점이다.

위의 그래프를 보면 A-C-B-G가 올바른 최단 경로이며, 비용은 4 + (-3) + 1 = 2이다.

 

다익스트라 알고리즘

하지만 다익스트라 알고리즘을 적용해 보면 위의 그래프 처럼 된다. 시작점 A에서 종점 G까지의 최단 경로가 A-B-G이고, 그 비용은 3이라고 한다. 이는 틀린답이다.

 

위 그래프를 풀이하면 시작점 A에서 B와 C가 후보가 되었을 때, B의 비용이 더 작기 때문에 A-B라는 경로를 선택한다.

사실 A-C-B로 멀리 돌아가는 것이 음의 비용이 포함되어 총 비용이 작아지지만, 다익스트라 알고리즘은 이 시점에서 간선(C, B)의 존재를 모르기 때문에 틀린 결론을 도출하게 된것이다.

 

또한 최단 경로 문제에서 비용이 음수인 폐로가 있으면 벨먼-포드 알고리즘은 그 폐로를 계속 순회에 최단 경로가 없다는 것을 판단할 수 있지만, 다익스트라 알고리즘은 최단 경로가 존재하지 않는데도 잘못된 최단 경로를 도출한다. 따라서 다익스트라 알고리즘은 음의 비용을 포함하는 그래프에서 사용할 수 없다.

 

정리하면 비용이 음수인 간선을 포함하지 않는 경우에는 계산시간이 적은 다익스트라 알고리즘을 사용하는 것이 좋지만, 음수인 간선을 포함하는 경우에는 계산 시간이 오래 걸려도 정확한 답을 찾아주는 벨먼-포드 알고리즘을 사용하는 것이 좋다.

---

⏱️ 시간복잡도

다익스트라 알고리즘은 주어진 그래프의 정점 수를 n, 간선 수를 m이라고 했을 때 계산 시간은 O(n²)이지만, 효율적인 데이터 구조를 사용하면 O(m+n log n)이 된다.

 

---

참고 자료

그림으로 이해하는 알고리즘 : 이시다 모리테루, 미야자키 슈이츠