다익스트라 알고리즘이란?
다익스트라 알고리즘은 에츠허르 다익스트라가 고안한 알고리즘으로 하나의 시작 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘이다. (단 음의 가중치를 갖는 간선이 없어야 한다.).
처음 다익스트라 알고리즘은 O(V^2)의 복잡도를 가졌었지만 우선순위 큐를 사용하여 O(E+VlogV)까지 시간 복잡도를 줄일 수 있게 되었다.
백준 기준으로 골드 3 ~ 골드 1 정도의 문제를 풀다 보면 다익스트라 알고리즘을 활용해서 풀어야 하는 문제들을 접할 수 있으며 개발자라면 알아야 할 것 같은 알고리즘 중 하나라고 생각하기도 하고 자꾸 문제를 푸는데 다익스트라 알고리즘을 정확하게 이해하고 있지 못하고 있는 것 같아서 포스팅을 남기게 되었다.
다익스트라 알고리즘의 탐색 과정
아래와 같은 정점과 간선들이 있습니다. 아래의 그래프에서 정점 A에서 다른 모든 정점까지의 최단거리를 구하려고 합니다.
먼저, 출발점 A를 방문하고 A에서 출발하는 간선들을 추가해 줍니다.
추가된 간선들을 통해 도달할 수 있게 된 정점 B, C, D까지의 최단거리를 갱신해 줍니다. 여기서 다음으로 어느 정점을 방문해야 할까요?
다익스트라 알고리즘에서는 도달할 수 있는 정점 중 가장 최단거리가 짧은 노드를 우선순위로 방문합니다. 따라서 간선 AD를 타고 D를 방문하게 됩니다.
D를 방문하였으니 전과 마찬가지로 D에서 시작하는 간선을 추가하고 아직 방문하지 않은 정점(노란색으로 마킹하지 않은 정점) 중 가장 가까운 정점을 찾아 방문하게 됩니다.
똑같이 진행해 줍니다. C를 방문하게 되면서 정점 E에 도달할 수 있게 되었는데 이때 정점 E의 최단거리는 C의 최단거리(3) + 간선 CE(3) = 6이 됩니다. 다음 정점은 아직 방문하지 않았고 방문할 수 있는 B와 G 중 더 최단거리가 짧은 B가 되겠습니다.
B를 방문하면서 F에 도달할 수 있게 되었습니다. F의 최단거리를 B의 최단거리(5) + 간선 BF(7) = 12로 갱신해 줍시다.
또 이번에는 간선 BE를 통해 E로 도달할 수 있게 되었습니다. 하지만 현재 E의 최단거리인 6이 B의 최단거리(5) + 간선 BE(2) = 7 보다 짧기 때문에 갱신해 주지 않습니다. 만약 B + BE가 6보다 작았다면 더 짧은 최단거리이므로 갱신이 되었겠죠? 하지만 B를 통해 E로 가는 길은 최단거리가 아니었기 때문에 그냥 넘어가 줍니다.
이번엔 E를 방문하게 되면서 E를 통해 F로 가는 길을 찾았습니다. 이번 경우에는 기존 F의 최단거리인 12가 E의 최단거리인 6과 간선 EF의 길이 4의 합인 10보다 크기 때문에 F의 최단거리를 10으로 갱신해 줍니다. 그 후 전과 동일하게 남아있는 정점 F와 G 중 더 짧은 최단거리를 가진 F를 방문합니다.
F를 방문하니 F를 통해 G로 방문하는 길이 생겼습니다. 이번 경우에도 F를 통해 G로 도달하는 거리가 기존 G의 최단거리보다 짧아 G의 최단거리 값을 갱신해 줍니다. 이제 남은 정점은 G밖에 없으니 G를 방문해 줍니다.
이제 모든 정점을 방문하였습니다. 다익스트라 알고리즘은 모든 정점을 방문하게 되면 탐색을 종료합니다.
표를 한번 보면 A로부터 모든 정점까지의 최단거리를 확인할 수 있습니다. 이때 최단 경로는 빨간색 간선들을 통해 정점까지 도달하는 경로가 됩니다.
끝내며..
원래 위 그림들을 피피티 형식으로 샥샥 넘겨가면서 봐야 이해가 더 잘 될 거같은데 그렇게 올릴 수가 없어서 좀 아쉽다,, 그래서 슬라이드를 움짤로 만들어봤는데 글씨가 잘 안 보이긴 한다..
아무튼 다익스트라에 대한 포스팅은 이 정도로 끝내겠다. 다익스트라 알고리즘이 길 찾기 알고리즘 중에 가장 대표적이고 쉬운 알고리즘에 속한다.
다익스트라 알고리즘은 하나의 정점에서 다른 정점까지의 최단거리를 구해주는 반면에 모든 정점 쌍들 간의 거리를 구해주는 플로이드-워셜 알고리즘, 음의 가중치를 가진 간선에서도 최단거리를 구해주는 벨만-포드 알고리즘 그리고 다익스트라 알고리즘의 심화판인 A* 알고리즘 등 더 어렵고 신기한 알고리즘들도 있다.
다음에 기회가 되면 다른 길 찾기 알고리즘에 대해 탐구해 보는 시간을 가져보도록 해보겠다.