간선 수와 비용
A에서 C로 가는 직접 간선의 비용이 9이고 A→B와 B→C의 비용이 각각 2라면 두 간선을 거친 비용 4가 더 작다. 가장 적은 간선을 쓰는 경로가 가장 작은 가중치 합을 갖는 것은 아니다.
연결되지 않은 경우
출발점에서 도착점으로 갈 수 없다면 그 둘 사이의 경로 자체가 없다. 알고리즘에서는 도달 불가를 별도로 표시한다. 임의의 큰 수를 실제 경로 비용처럼 해석해서는 안 된다.
방향과 가중치 조건
유향 그래프에서는 간선 방향을 따라야 한다. 음수 가중치를 허용하는 문제에서는 출발점과 도착점 사이에 영향을 주는 음수 순환의 존재와 경로 반복 허용 여부 등을 확인해야 한다. 문제 조건에 따라 최솟값이 존재하지 않을 수 있다.
문제의 범위
한 쌍의 정점 사이, 한 출발점에서 모든 정점까지, 모든 정점 쌍 사이를 구하는 문제는 서로 다르다. 같은 최단 경로라는 이름 아래서도 필요한 결과와 그래프 조건에 맞춰 방법을 선택한다.
관련 문서
가중 그래프 / 유향 그래프 / 무향 그래프 / 최소 신장 트리 / 경로 그래프 / 정점 (그래프 이론) / 간선 (그래프 이론)