# All-Pairs

• 2026년 8월 11일 알고리즘
  모든 쌍 최단 거리 — 다익스트라 N번과 플로이드·워셜

  한 시작점이 아니라 모든 노드 쌍의 최단 거리를 구한다. 다익스트라를 N번 돌리는 기준선을 세우고, 경유할 수 있는 노드를 {1..k}로 제한해 k를 늘려 가는 플로이드·워셜을 유도한다. 점화식 D^k[i][j]=min(D^{k-1}[i][j], D^{k-1}[i][k]+D^{k-1}[k][j])가 왜 성립하는지 양방향으로 증명한다.