서론
여러분들이 현재 여행을 가고 싶은, 혹은 약속이 있어 가야 하는 목적지가 있습니다.
이때 여러분들은 어떻게 목적지를 향해 가십니까???
그냥 무작정 그 목적지가 있는 방향을 향해 걸어갈 수도 있지만, 대부분 사람들은 길 찾기 앱을 혹은 웹을 켜서 추천 경로를 보고 갈 것입니다.
그리고 이 추천 경로 중 자신이 생각하는 가중치가 (시간, 비용 혹은 걷는 거리 등등) 가장 높은 경로를 따라가겠죠.
이 경로를 찾는 방법이 바로 다익스트라 알고리즘입니다.
다익스트라 알고리즘
다음과 같은 그래프가 있고, 저는 A에서 G로 가야 하는 상황이라고 가정해보겠습니다.
시작하기 전에 다음과 같은 표를 초기화해주겠습니다.
D[V], P[V], V[V]가 의미하는 것은 다음과 같습니다.
- D[V]: 출발지에서 정점 V까지 가는 거리
- P[V]: 정점 V로 오는데 가장 적은 거리로 오는 정점
- V[V]: 정점 V에 방문했는지 여부
초기화를 했으니 이제 그래프를 탐색해볼까요~~?
A에서 출발하기 때문에 A로 가야 하는 거리를 0으로 초기화해주겠습니다.
A에서는 B와 C로 갈 수 있네요?
B로 가는 거리와 C로 가는 거리를 갱신해 주겠습니다.
음... 저희에게는 B에서 출발하는 선택지와 C에서 출발하는 선택지가 있는데 어떤 선택지를 골라야 할까요..?
정답은 B입니다. 다익스트라 알고리즘은 미래를 생각하지 않고 현재 단계에서 가장 최선의 길을 선택하는 그리디 알고리즘을 기반으로 하기 때문이죠
그럼 이제 정점 B와 연결된 정점을 탐색해볼까요?
자 다음으로 가장 작은 거리인 정점 C와 D를 탐색해주겠습니다.
먼저 정점 C를 탐색하겠습니다.
오 정점 C를 탐색했는데 도착지에 도착했네요.
그러면 여기서 탐색을 그만해야 할까요??
아닙니다. 다른 정점에서 더 짧은 거리로 도착할 수 있기 때문이죠.
그럼 아직 탐색하지 못한 정점을 탐색해주겠습니다.
D에서도 정점 G에 갈 수 있네요. 하지만 D를 통해 갈 수 있는 거리가 C를 통해 오는 거리보다 크기 때문에 갱신해 주지 않겠습니다.
정점 G에선 갈 수 있는 길이 없으니 방문 처리만 해주고 나머지 정점에 대해 탐색해주겠습니다.
자 이렇게 그래프에 있는 모든 정점에 대해 탐색을 완료했습니다.
이렇게 출발점에서 도착지까지 최소 거리는 5라고 알게 되었네요.
마지막으로 출발점에서 도착지까지 어떤 정점을 통해 가야 하는지 알고 싶을 수 있습니다.
그때는 거꾸로 찾으면 됩니다.
도착지 G로 최단 거리로 오려면 C를 거쳐와야 하고,
C를 최단 거리로 오려면 A를 통해 와야 합니다.
그래서 A -> C -> G 이렇게 가게 된다면 최단 거리로 도착할 수 있습니다.
마치며
다익스트라 알고리즘은 가중치가 양수일 때 사용이 가능합니다.
가중치가 음수가 포함된 경우엔 벨만 포드 알고리즘을 사용해야 하는데 궁금하시다면 여기서 확인하실 수 있습니다.
최대한 열심히 작성하였으나 사람이다 보니 부족한 점이 있을 수 있습니다.
부족한 점을 발견하신다면 말씀해주세요.
바로 고치도록 하겠습니다.
감사합니다.
