[자료구조] 최단 경로 알고리즘

그래프에서 어떤 노드에서 어떤 노드로 가는 경로 중 가장 짧은 경로를 찾는 알고리즘은

여러 조건에 따라 방법이 다양하다.

 

그 중 BFS를 이용하는 방법과 Dijkstra에 대해 알아보자.

---

BFS를 이용한 최단 경로 알고리즘

 

BFS에서 각 노드에 멤버변수로 predecessor를 추가한다. 해당 멤버변수에는 해당 노드가 어떤 노드로부터 왔는지 기록된다. 즉, Root노드를 제외한 모든 노드들은 BFS를 할 때 특정 노드에서부터 탐색되어져 나온 것이므로, 이를 기록하는 것이다. 

 

이 결과로 특정 노드에서 predecessor를 따라 거꾸로 올라감으로서 특정 노드로 가는 최단의 경로를 알 수 있다. 이를 특별히 backtracking이라고 부르기도 한다.

 

단, 이는 주로 root노드를 출발점으로 보았을 때 사용되는 방법이고, 엣지에 가중치가 있어선 안된다.

---

Dijkstra 최단 경로 알고리즘

 

이는 가중치가 있는 경로에서도 활용할 수 있다.

 

멤버변수로 distance, predecessor, complete를 추가로 가진다. distance는 현재까지 확인된 최단거리를 표시하는 것이다. predecessor는 현재까지 확인된 최단거리에서 이전에 방문한 노드를 말한다. 그리고 complete는 가능한 모든 경우를 확인하여 최단거리가 확보되었다는 의미이다. 

 

위의 추가된 멤버변수(그 중에서도 complete)로도 예상할 수 있듯이, Dijkstra는 경로를 모두 확인하여 가장 짧은 경로를 찾아내는 방식으로 수행된다.

 

이 때 각각의 엣지를 확인하고 노드의 distance값을 업데이트하는 과정을 Relaxation이라고 한다. 풀어서 이야기할 때는 '엣지(A,B)를 relax한다.'라고도 한다.

 

참고로 distacne을 최초값은 무한대(혹은 그에 준하는 수)로 놓는 것이 좋다. 초기값은 무조건 업데이트가 되어야 최단거리를 찾을 수 있기 때문이다.

---

Dijkstra 최단 경로 알고리즘 수행과정

 

0. root노드의 distance를 0으로, predecessor를 None으로 초기화한다.

1. comlete하지 않은 노드 중 가장 distance값이 가작 작은 노드를 선택한다.

2. 해당 노드에 인접한 complete하지 않은 노드를 돌면서 해당 노드를 relax한다.

3. 해당 노드를 complete한다.

4. 1~3의 과정을 모든 노드가 complete될때까지 반복한다.