정의. 무방향 그래프에서 정점 $a$와 $b$ 사이의 최단 경로란 두 정점 사이의 경로 중 간선의 개수가 가장 적은 경로를 말합니다.
문맥에 따라 경로의 길이는 간선의 수($k$), 중간 정점의 수($k-1$), 또는 시작점과 끝점을 포함한 전체 정점의 수($k+1$)를 의미할 수 있습니다.
두 정점 사이의 최단 경로가 항상 유일한 것은 아닙니다.
정의. 가중 그래프란 각 간선에 가중치, 길이 또는 비용이라고 부르는 수가 대응되는 그래프입니다.
가중 그래프에서 경로의 길이는 그 경로에 속한 모든 간선의 길이의 합을 말합니다.
별도로 언급하지 않는 한, 간선의 길이는 음수를 포함하여 어떤 수든 될 수 있습니다. 음수 간선이 있는 그래프에서는 직관에 반하는 상황이 생길 수 있습니다. 음수 가중치의 사이클이 있으면 그 사이클을 끝없이 돌 수 있고, 따라서 두 정점 사이를 이동하는 도중에 이 사이클을 여러 번 지나면 임의로 작은 가중치의 경로를 얻을 수 있습니다. 그래서 보통은 간선의 길이가 음수가 아닌 그래프를 다룹니다.
그래프에서 최단 경로를 찾아야 하는 경우가 많습니다. 이 문제에는 서로 밀접하게 관련된 몇 가지 변형이 있습니다:
- 주어진 정점 쌍 $a$와 $b$ 사이의 최단 경로를 찾는 것입니다.
- 그래프에서 주어진 정점 $a$와 나머지 모든 정점 사이의 최단 경로 찾기.
- 그래프의 모든 정점 쌍 사이의 최단 경로를 찾는 문제입니다.
이 장에서는 이 문제와 그 밖의 관련 문제를 해결하기 위한 몇 가지 고전적인 알고리즘을 살펴보겠습니다.