[최단경로] 01.최단경로를 위한 알고리즘 소개

이번 포스트에서는 알고리즘 문제에 자주 나오는 "최단 경로"문제를 해결하기 위한 알고리즘들에 대해서 살펴보자.

 

최단 경로란?

 

최단 경로란 그래프를 탐색하면서 임의의 두 정점 사이에 다양한 간선의 조합 중 간선의 가중치의 합이 최단인 경로를 의미한다. 이 최단거리를 구할 때는 크게 간선의 가중치가 없는 경우와 있는 경우 두 가지 경우로 나눌 수 있다.

 

가중치가 없는 그래프

가중치가 없는 경우 즉 모든 정점간의 이동 비용이 동일한 경우는 BFS 탐색이 가장 간단하다. 이때 BFS의 depth가 총 비용이 된다. 예를 들어 아래와 같은 그래프를 살펴보자.

만약 서울에서 출발해서 부산에 도착하는데 각 도시 간 이동 비용이 동일하다면 서울에서 원주, 대구를 찍고 부산에 도착하는게 depth(==비용) 3으로 가장 짧다. 그리고 이런 탐색에는 BFS가 적합하다.

 

가중치가 있다면?

하지만 가중치가 있다면 어떻게 될까?

위와 같이 도시간 이동 비용이 그래프에 반영된다면 이제 서울에서 이천, 구미, 대구를 거쳐서 부산을 가는 비용이 depth는 4이지만 비용은 5로 다른 경로를 통한 탐색보다 저렴하게 이동할 수 있다. 즉 depth를 이용한 결과와 비용을 합한 결과가 달라지게되었다. 따라서 가중치가 있는 그래프에서는 BFS를 이용해서는 최단거리를 구할 수 없다.

 

그럼 어쩔?

가중치가 있는 그래프의 최단경로를 구하기 위해서는 다음과 같은 3가지 이미 잘 알려진 그리디 알고리즘들을 이용한다. 

• 한 점에서 다른 모든 정점들까지의 최단 경로
  • 다익스트라(Dijkstra) 알고리즘은 모든 간선이 양의 가중치로만 구성된 경우 사용되며 음의 가중치에는 사용할 수 없다.
  • 벨만-포드(Bellman-Ford)알고리즘은 음의 가중치를 허용하는 알고리즘으로 음의 간선 순환이 있을 때도 사용할 수 있다. (음의 간선 순환일 경우 최단 거리를 구하지는 못한다. 단지 감지할 뿐)
• 모든 점에서 모든 점까지의 최단 경로
  • 플로이드-워셜(Floyd-Warshall) 알고리즘은 음의 가중치도 가능한데 음의 가중치의 싸이클이 있는 경우는 사용할 수 없다.

 

위 알고리즘들이 어떻게 동작하는지 하나씩 살펴보자.