[알고리즘] 최단 경로 알고리즘
최단 경로 알고리즘이란?
최단 경로 알고리즘이란, 두 노드를 잇는 가장 짧은 경로를 찾는 문제이다.
- 정점(Node): 노드, 경로에서 하나의 지점
- 간선(Edge): 두 노드를 잇는 길
- 가중치(Weight): 간선의 크기(거리)
가중치가 있는 그래프에서는 간선 가중치의 합이 최소가 되도록 하는 경로를 찾는 것이 목적이다.
Optimal Substructure
최단 거리의 가장 중요한 속성은 다음과 같다.
- 최단 경로의 부분 경로는 최단경로이다.
예를 들어, A 에서 Z 로의 최단 경로를 구했을 경우, A → B → F → Z 라고 하자. 이때 A에서 F 까지의 최단경로는 A → B → F 라는 것이다. 또한 B에서 Z 까지의 최단 경로 또한 B → F → Z 가 되는 것이다.
왜냐하면, A에서 F로 까지의 더 짧은 최단 경로가 다른 것이 존재한다면, 이것은 결국 Z까지의 최단 경로도 달라지는 것과 같은 결과를 내놓는 것과 같다.
이와 같이, 어떤 문제의 최적 해가, 그 부분 문제들의 최적해들로 구성된다면, 해당 문제는 optimal substructure를 가진다고 말한다. 이를 이용해 Greedy, DP를 이용해 문제를 효과적으로 풀어낼 수 있다.
Edge Relaxation
최단 경로를 구하는 알고리즘은 edge relaxation을 기본 연산으로 한다. Edge relaxation이란, 최단 경로 알고리즘을 수행하는 과정에서 경로를 구성하고 있는 간선 가중치의 합을 줄여나간다는 의미로 볼 수 있다.
위 예시에서, A → B → F → Z 가 최단 경로였다고 해보자. 그런데 다른 노드를 탐색해보니 A에서 F까지의 경로중, A → C → D → F 의 간선 가중치의 합이 적다는 것을 알아냈다고 하자. 그럴 경우 A → F, A → Z까지의 최단경로를 구성하고 있는 노드와, 간선 정보, 그리고 거리의 합(가중치의 합)을 업데이트 해준다. 간선 가중치의 합을 줄여나가는 edge relaxtion을 통해 최단 경로, 거리를 구할 수 있게 된다.
상세 알고리즘
최단 경로 알고리즘에는 그래프의 특성에 따라 여러 알고리즘을 사용하여 구현할 수 있다.
모든 간선의 가중치가 같은 경우(주로 모두 1인 경우)
- BFS
하나의 정점에서 모든 정점으로의 최단 경로
- 다익스트라(Dijkstra), Bellman-Ford
모든 정점에서 모든 정점으로의 최단 경로