← 21주차 · 최단 경로와 위상 정렬
어려움그래프플로이드-워셜DP

모든 쌍 최단 거리

정점 개수 n과 방향 간선 목록 edges가 주어져요. edges의 각 원소 [u, v, w]는 u에서 v로 가는 비용 w인 간선이에요. 같은 쌍을 잇는 간선이 여러 개면 가장 싼 것만 의미가 있어요.

모든 정점 쌍 (i, j)에 대한 최단 거리를 n × n 표로 반환해요. i에서 i까지는 0이고, i에서 j로 갈 수 없으면 -1로 표시해요.

핵심은 '경유지를 하나씩 늘려 가는 것'이에요. i에서 j로 갈 때 k를 거치는 게 더 싸면 갱신해요. 이때 경유지 `k` 루프가 가장 바깥에 와야 해요. 순서를 바꾸면 틀려요.

예시

예시 1
입력
n = 3, edges = [[0, 1, 4], [1, 2, 1], [0, 2, 10]]
출력
[[0, 4, 5], [-1, 0, 1], [-1, -1, 0]]
설명
0→2는 직행 10보다 1을 거쳐 5가 싸요. 2에서는 아무 데도 못 가요.
예시 2
입력
n = 2, edges = []
출력
[[0, -1], [-1, 0]]

제한 사항

  • 1 ≤ n ≤ 400
  • 0 ≤ edges.length ≤ n × n
  • 0 ≤ u, v < n, -10,000 ≤ w ≤ 10,000, 음수 사이클은 없어요.
거리 표를 무한대로 채우고 대각선을 0으로, 간선마다 더 싼 값으로 초기화해요. 그다음 경유지 k를 가장 바깥 루프로 두고 i, j를 돌며 dist[i][k] + dist[k][j]가 더 작으면 갱신해요. 끝나고 무한대는 -1로 바꿔요.
javascript
function floydWarshall(n, edges) {
  const INF = Infinity;
  const dist = Array.from({ length: n }, () => new Array(n).fill(INF));
  for (let i = 0; i < n; i++) dist[i][i] = 0;
  for (const [u, v, w] of edges) {
    if (w < dist[u][v]) dist[u][v] = w;
  }
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }
  return dist.map((row) => row.map((x) => (x === INF ? -1 : x)));
}
이전 문제수강 과목 순서
다음 문제유니온 파인드 구현
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.