중간 정점을 늘린다
현재 허용된 정점들만 중간에 거칠 수 있다고 생각한다. 새 정점 k를 허용할 때 i에서 j로 가는 기존 후보와 i에서 k를 거쳐 j로 가는 후보를 비교한다. 더 짧은 쪽을 저장한다.
갱신식
핵심 갱신은 d[i][j]를 d[i][j]와 d[i][k]+d[k][j] 중 작은 값으로 바꾸는 것이다. 기본 구현에서는 중간 정점 k를 가장 바깥 반복으로 두어 단계의 의미를 유지한다. 도달 불가 값의 덧셈도 적절히 처리해야 한다.
초깃값
자기 자신까지의 거리는 보통 0, 직접 간선이 있으면 그 가중치, 경로가 아직 없으면 도달 불가로 시작한다. 같은 두 정점 사이에 여러 간선이 있다면 초기 직접 비용은 가장 작은 값을 사용한다.
음수 가중치와 순환
음수 간선 자체는 허용할 수 있다. 그러나 음수 순환의 영향을 받는 정점 쌍에는 유한한 최단 거리 해석이 성립하지 않을 수 있다. 계산 후 음수가 된 대각 원소는 음수 순환의 존재를 확인하는 단서가 된다.
관련 문서
최단 경로 / 가중 그래프 / 유향 그래프 / 벨만-포드 알고리즘 / 동적 계획법 / 다익스트라 알고리즘 / 시간 복잡도