DEV Community

1 1

ベルマンフォード法 (Bellman-Ford algorithm)

コード

let v = 0, e = 0, r = 0
let path = []

process.stdin.resume();
process.stdin.setEncoding("utf-8");

process.stdin.on("data", function (input) {
  let num = 0
  const lines = input.split("\n")
  for (const line of lines) {
    if (line === "") {
      break
    }
    const m = line.split(" ").map(v => parseInt(v))
    if (num === 0) {
      v = m[0]
      e = m[1]
      r = m[2]
    } else {
      path.push(m)
    }
    num++
  }
});

process.stdin.on("end", function () {
  // console.log(v, e, r)
  // console.log(path)
  bellmanFord(v, r, path)
});

/**
 * @param {number} v 
 * @param {number} r 
 * @param {number[][]} path 
 */
function bellmanFord(v, r, path) {
  const inf = Number.MAX_SAFE_INTEGER
  const dist = Array(v).fill(inf)
  dist[r] = 0
  for (let i = 0; i < v; i++) {
    let change = false
    for (const [s, t, d] of path) {
      if (dist[s] === inf) {
        continue
      }
      if (dist[s] + d < dist[t]) {
        if (i + 1 === v) {
          console.log('NEGATIVE CYCLE')
          return
        }
        dist[t] = dist[s] + d
        change = true
      } else {
        continue
      }
    }
    if (!change) {
      break
    }
  }
  for (const d of dist) {
    console.log(d === inf ? 'INF' : d)
  }
}

問題

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more