5.2.1 최단 경로

경로(path)란 시작 버텍스와 끝 버텍스 사이에 있는 일련의 연속적인 버텍스들을 의미합니다. 경로상에 있는 버텍스의 집합을 p라고 하겠습니다. 동일한 버텍스는 경로에서 단 한 번만 등장해야 합니다. 즉, p는 중복된 버텍스를 허용하지 않습니다.

경로의 길이는 이를 구성하는 엣지의 개수입니다. 모든 가능한 경로 중에서 가장 거리가 짧은 경로를 최단 경로(shortest path)라고 합니다. 최단 경로 계산은 그래프 이론 알고리즘에서 상당히 자주 사용하지만 그 계산이 항상 쉬운 것은 아닙니다. 시작 버텍스와 끝 버텍스를 잇는 최단 경로를 계산하는 방법은 여러 가지입니다. 그 중에서 가장 인기 있는 최단 경로 탐색 알고리즘은 1950년대 후반에 고안된 다익스트라 알고리즘(Dijkstra’s algorithm)입니다. 다익스트라 알고리즘은 범지구위치결정시스템(Global Positioning System, GPS)이나 네트워크 라우팅 알고리즘 등 다양한 분야에서 널리 사용되고 있습니다.

이 장의 후반부에서 다룰 너비 우선 검색(Breadth-First Search, BFS) 알고리즘을 약간 수정하면 다익스트라 알고리즘이 됩니다. BFS는 그래프상에 있는 모든 엣지의 이동 비용은 동일하다는 가정을 사용합니다. 이와 달리 다익스트라 알고리즘은 엣지의 이동 비용이 다양한 네트워크에도 적용할 수 있습니다.

다익스트라 알고리즘은 단일 출발지(single source)로부터의 최단 경로를 계산하는 알고리즘입니다. 만약 모든 출발지-도착지 쌍의 최단 경로를 구하고 싶다면 플로이드-워셜(Floyd-Warshall) 알고리즘을 쓰는 것이 좋습니다.