11-1. 가중치 그래프에서의 최단 경로

최단 경로란?

최단 경로(shortest path) 문제는 가중치 그래프에서 정점 u와 정점 v를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제이다.

이때 간선의 가중치는 보통 비용이나 거리, 시간 등을 나타낸다.

지도를 가중치 그래프로 나타낸다고 하면, 지도의 각 지역들은 그래프의 정점을 나타내고 가중치(간선)는 어떤 지역에서 다른 지역으로 이동하는 거리를 의미한다.

일반적으로 지도에서 출발점과 도착점을 설정하면 최단 경로를 보여준다.

숭실대입구역에서 서울대입구역으로 가는 경로는 엄청나게 많겠지만, 최단 경로는 많지 않을 것이다.

(경로 상의 가중치 합이 같은 경로가 여러 개 있을 수도 있음)

---

최단 경로 알고리즘

최단 경로를 구하는 대표 알고리즘으로는 Dijkstra와 Floyd 두 가지가 있다.

 

Dijkstra 알고리즘은 하나의 시작 정점에서 다른 정점까지의 최단 경로를 구한다.

Floyd 알고리즘은 모든 정점에서 다른 모든 정점까지의 최단 경로를 구한다.

 

두 알고리즘에 대해 자세히 알아보자.