[자료구조] 최단 경로
자료구조에는 최단 경로라는 개념이 있습니다. 이 글에서는 최단 경로에 대해서 알아보겠습니다.
최단 경로란?
사실 어려울 것 없이 말 그대로입니다. 네트워크에서 정점을 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로입니다.
이러한 최단 경로를 구하는 알고리즘이 몇 가지 있는데, 가장 대표적인 다익스트라 (Dijkstra) 알고리즘을 알아보겠습니다.
다익스트라(Dijkstra)의 유례?
다익스트라알고리즘은 '에츠허르 다익스트라'(정확한 발음은 '데이크스트라'라고 합니다.)라는 컴퓨터 과학자가 고안해 낸 알고리즘입니다. 알고리즘의 이름도 저 사람의 이름에서 따온 것이죠.
처음 고안된 이후 계속해서 수정되면서 현재는 빠르게 도달하는 경로를 찾아내는 대부분의 문제에 이용되는 가장 대표적인 최단 경로 탐색 알고리즘이 되었습니다.
그래서 다익스트라(Dijkstra)가 뭔데?
잡소리가 길었으니 바로 시작해 보죠.
다익스트라 알고리즘은 시작 정점에서 모든 다른 정점까지의 최단 경로는 찾는 알고리즘입니다.
모든 상황에서 가장 비용이 적은 노드를 선택하며 경로를 찾아가는 것이죠.
간단히 사진을 하나 봅시다.
위 그림을 보면 노드가 4개 있고 노드를 이어주는 간선이 있습니다.
시작 정점 A에서 모든 다른 정점까지의 최단 경로를 찾아봅시다.
우선 A에서 갈 수 있는 노드는 B, C, D 모두 갈 수 있습니다. 최단 경로를 찾아야 하기에 하나씩 비교해 보면
A->B는 2
A->C는 7
A->D는 10입니다.
즉, A에서 B로 가는 것이 최단 경로이기에 A에서 B로 이동합니다.
이제 B에서 갈 수 있는 노드를 봅시다.
다시 돌아가지는 않기에 A를 제외하면 C밖에 남지 않습니다. 그렇다면 C로 이동을 할 텐데...
여기서!
헷갈리면 안 되는 점이 하나 있습니다. 바로 B에서 C가 4이기 때문에 가중치를 4로 생각하시는 분들이 많을 텐데요.
B는 A를 거쳐서 왔기 때문에 전의 값을 더해주어야 합니다. 즉, 2 + 4 = 6이 되는 것입니다.
사실 여기서 하나를 더 확인해 보아야 합니다.
바로 A에서 C로 가는 루트랑 비교해서 어느 값이 더 작은지 확인해 봐야 합니다.
여기서는 A->C는 7, A->B->C는 6이기에 신경을 쓸 필요가 없습니다.
이제 남은 노드는 D밖에 없습니다.
D도 C와 같이 A->D와 A->B->C->D를 확인해 봅시다.
A->D는 10
A->B->C->D는 2 + 4 + 1 = 7입니다.
그러니 A->B->C->D를 마지막으로 경로 탐색을 종료합니다.
최단 경로가 발견된 정점 집합을 표로 정리해 보면,
위의 그림과 같이 나올 것입니다.
마무리
지금까지 다익스트라 알고리즘에 대해 알아보았습니다.
솔직히 저도 이해를 완전히 하진 못했습니다. 그래서 글을 쓰는 지금도 이걸 올려도 되나?라는 생각이 듭니다.
여하튼 오늘 글은 여기까지입니다.