그래프 알고리즘 중에서 MST와 함께 유명한 알고리즘으로 최단 경로 알고리즘이 있습니다. 최단 경로 알고리즘에서는 방향 그래프이자 가중치 그래프를 기본적으로 사용합니다. 참고로 그래프에 음수 사이클은 있을 수 없습니다. 음수 사이클이란 다음 그림과 같은 사이클을 의미합니다.

▲ 그림 14-1 음수 사이클

최단 경로에서 경로란 에지들의 가중치 합을 의미합니다. 그림 14-1과 같이 그래프에 음수 사이클이 있다면 이 사이클을 돌면 돌수록 거리는 짧아집니다. 이 그림에서는 -5만큼 계속 짧아지는 것이지요. 달리면 달릴수록 짧아지는 거리는 있을 수 없습니다. 하지만 음수 에지는 있을 수 있습니다. 알고리즘에 따라 음수 에지를 인정하는 알고리즘도 있고 인정하지 않는 알고리즘도 있습니다.

최단 경로 알고리즘에는 몇 가지 종류가 있습니다. 먼저 하나의 출발점에서 나머지 모든 목적지에 대한 최단 경로를 구하는 알고리즘이 있습니다. 이 알고리즘에는 데이크스트라와 벨만 포드 알고리즘이 유명합니다. 두 번째로 모든 (출발지, 목적지) 쌍에 대한 최단 경로를 구하는 알고리즘이 있습니다. 플로이드 워셜 알고리즘이 유명합니다. 다이나믹 프로그래밍의 대표적인 예이기도 합니다. 이 책에서는 데이크스트라 알고리즘만 알아보겠습니다.