← 21주차 · 최단 경로와 위상 정렬
보통그래프벨만-포드

음수 간선이 있는 최단 경로

정점 개수 n, 방향 간선 목록 edges, 시작 정점 start가 주어져요. edges의 각 원소 [u, v, w]는 u에서 v로 가는 비용 w인 간선이고, w는 음수일 수도 있어요.

start에서 각 정점까지의 최단 거리를 배열로 반환해요. 갈 수 없는 정점은 null로 표시해요. 단, start에서 도달할 수 있는 곳에 음수 사이클이 있으면(돌수록 거리가 계속 줄어드는 고리) 최단 거리가 정해지지 않으므로 숫자 -1을 반환해요.

음수 간선이 있으면 다익스트라가 깨져요. 대신 모든 간선을 훑으며 거리를 줄이는 일을 n-1번 반복해요. 그러고도 한 번 더 줄어드는 간선이 있으면 음수 사이클이에요.

예시

예시 1
입력
n = 3, edges = [[0, 1, 4], [0, 2, 5], [1, 2, -3]], start = 0
출력
[0, 4, 1]
설명
0→1(4)→2(-3)로 2까지 1이 돼요. 0→2 직행 5보다 싸요.
예시 2
입력
n = 2, edges = [[0, 1, 1], [1, 0, -3]], start = 0
출력
-1
설명
0↔1을 돌면 비용이 계속 줄어드는 음수 사이클이에요.

제한 사항

  • 1 ≤ n ≤ 1,000
  • 0 ≤ edges.length ≤ 10,000
  • 0 ≤ u, v, start < n, -10,000 ≤ w ≤ 10,000
거리 배열을 무한대로, 시작점을 0으로 둬요. n-1번 반복하며 모든 간선 [a, b, w]에 대해 a에 도달했고 dist[a] + w < dist[b]면 줄여요. 그 뒤 한 번 더 돌려서 여전히 줄어드는 간선이 있으면 -1을 반환하고, 아니면 무한대를 null로 바꿔 반환해요.
javascript
function bellmanFord(n, edges, start) {
  const dist = new Array(n).fill(Infinity);
  dist[start] = 0;
  for (let round = 0; round < n - 1; round++) {
    for (const [a, b, w] of edges) {
      if (dist[a] !== Infinity && dist[a] + w < dist[b]) dist[b] = dist[a] + w;
    }
  }
  for (const [a, b, w] of edges) {
    if (dist[a] !== Infinity && dist[a] + w < dist[b]) return -1;
  }
  return dist.map((x) => (x === Infinity ? null : x));
}
이전 문제다익스트라 최단 경로
다음 문제수강 과목 순서
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.