가중치 그래프

간선마다 숫자(가중치)가 붙은 그래프다. 가중치는 거리 · 시간 · 비용처럼 그 간선을 지나는 값이고, 최단 경로는 지나간 간선의 가중치 합이 가장 작은 경로를 말한다. 가중치가 음수인 간선을 음수 간선이라 한다. 가중치 합이 음수인 사이클(음수 사이클)이 있으면 그 사이클을 돌 때마다 합이 계속 작아져서 최단 경로가 정해지지 않는다.