type Edge struct {
from, to, weight int
}
// bellmanFord returns shortest distances from src. ok is false if a negative
// cycle is reachable (then distances are undefined).
func bellmanFord(n int, edges []Edge, src int) (dist []int, ok bool) {
}type Edge struct {
from, to, weight int
}
// bellmanFord returns shortest distances from src. ok is false if a negative
// cycle is reachable (then distances are undefined).
func bellmanFord(n int, edges []Edge, src int) (dist []int, ok bool) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows an int.
}type Edge struct {
from, to, weight int
}
// bellmanFord returns shortest distances from src. ok is false if a negative
// cycle is reachable (then distances are undefined).
func bellmanFord(n int, edges []Edge, src int) (dist []int, ok bool) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows an int.
const inf = int(1e18)
dist = make([]int, n)
for i := range dist {
dist[i] = inf
}
}type Edge struct {
from, to, weight int
}
// bellmanFord returns shortest distances from src. ok is false if a negative
// cycle is reachable (then distances are undefined).
func bellmanFord(n int, edges []Edge, src int) (dist []int, ok bool) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows an int.
const inf = int(1e18)
dist = make([]int, n)
for i := range dist {
dist[i] = inf
}
// The only distance we know for sure: the source is 0 from itself.
}type Edge struct {
from, to, weight int
}
// bellmanFord returns shortest distances from src. ok is false if a negative
// cycle is reachable (then distances are undefined).
func bellmanFord(n int, edges []Edge, src int) (dist []int, ok bool) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows an int.
const inf = int(1e18)
dist = make([]int, n)
for i := range dist {
dist[i] = inf
}
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0
}type Edge struct {
from, to, weight int
}
// bellmanFord returns shortest distances from src. ok is false if a negative
// cycle is reachable (then distances are undefined).
func bellmanFord(n int, edges []Edge, src int) (dist []int, ok bool) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows an int.
const inf = int(1e18)
dist = make([]int, n)
for i := range dist {
dist[i] = inf
}
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
}type Edge struct {
from, to, weight int
}
// bellmanFord returns shortest distances from src. ok is false if a negative
// cycle is reachable (then distances are undefined).
func bellmanFord(n int, edges []Edge, src int) (dist []int, ok bool) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows an int.
const inf = int(1e18)
dist = make([]int, n)
for i := range dist {
dist[i] = inf
}
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for i := 0; i < n-1; i++ {
}
}type Edge struct {
from, to, weight int
}
// bellmanFord returns shortest distances from src. ok is false if a negative
// cycle is reachable (then distances are undefined).
func bellmanFord(n int, edges []Edge, src int) (dist []int, ok bool) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows an int.
const inf = int(1e18)
dist = make([]int, n)
for i := range dist {
dist[i] = inf
}
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for i := 0; i < n-1; i++ {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
}
}type Edge struct {
from, to, weight int
}
// bellmanFord returns shortest distances from src. ok is false if a negative
// cycle is reachable (then distances are undefined).
func bellmanFord(n int, edges []Edge, src int) (dist []int, ok bool) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows an int.
const inf = int(1e18)
dist = make([]int, n)
for i := range dist {
dist[i] = inf
}
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for i := 0; i < n-1; i++ {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
for _, e := range edges {
if dist[e.from] != inf && dist[e.from]+e.weight < dist[e.to] {
dist[e.to] = dist[e.from] + e.weight
}
}
}
}type Edge struct {
from, to, weight int
}
// bellmanFord returns shortest distances from src. ok is false if a negative
// cycle is reachable (then distances are undefined).
func bellmanFord(n int, edges []Edge, src int) (dist []int, ok bool) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows an int.
const inf = int(1e18)
dist = make([]int, n)
for i := range dist {
dist[i] = inf
}
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for i := 0; i < n-1; i++ {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
for _, e := range edges {
if dist[e.from] != inf && dist[e.from]+e.weight < dist[e.to] {
dist[e.to] = dist[e.from] + e.weight
}
}
}
// After n-1 rounds distances are final — UNLESS a negative cycle exists.
// One more relaxing pass: if anything still improves, such a cycle is
// reachable and "shortest path" is undefined.
}type Edge struct {
from, to, weight int
}
// bellmanFord returns shortest distances from src. ok is false if a negative
// cycle is reachable (then distances are undefined).
func bellmanFord(n int, edges []Edge, src int) (dist []int, ok bool) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows an int.
const inf = int(1e18)
dist = make([]int, n)
for i := range dist {
dist[i] = inf
}
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for i := 0; i < n-1; i++ {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
for _, e := range edges {
if dist[e.from] != inf && dist[e.from]+e.weight < dist[e.to] {
dist[e.to] = dist[e.from] + e.weight
}
}
}
// After n-1 rounds distances are final — UNLESS a negative cycle exists.
// One more relaxing pass: if anything still improves, such a cycle is
// reachable and "shortest path" is undefined.
for _, e := range edges {
if dist[e.from] != inf && dist[e.from]+e.weight < dist[e.to] {
return nil, false
}
}
return dist, true // O(V * E)
}# Each edge is a (u, v, weight) tuple: an edge u -> v.
# bellman_ford returns shortest distances from src, or None if a negative
# cycle is reachable (then distances are undefined).
def bellman_ford(n, edges, src):
pass# Each edge is a (u, v, weight) tuple: an edge u -> v.
# bellman_ford returns shortest distances from src, or None if a negative
# cycle is reachable (then distances are undefined).
def bellman_ford(n, edges, src):
# Every node starts unreachable. inf must be large but not so large that
# inf + weight overflows.
pass# Each edge is a (u, v, weight) tuple: an edge u -> v.
# bellman_ford returns shortest distances from src, or None if a negative
# cycle is reachable (then distances are undefined).
def bellman_ford(n, edges, src):
# Every node starts unreachable. inf must be large but not so large that
# inf + weight overflows.
inf = 10 ** 18
dist = [inf] * n# Each edge is a (u, v, weight) tuple: an edge u -> v.
# bellman_ford returns shortest distances from src, or None if a negative
# cycle is reachable (then distances are undefined).
def bellman_ford(n, edges, src):
# Every node starts unreachable. inf must be large but not so large that
# inf + weight overflows.
inf = 10 ** 18
dist = [inf] * n
# The only distance we know for sure: the source is 0 from itself.# Each edge is a (u, v, weight) tuple: an edge u -> v.
# bellman_ford returns shortest distances from src, or None if a negative
# cycle is reachable (then distances are undefined).
def bellman_ford(n, edges, src):
# Every node starts unreachable. inf must be large but not so large that
# inf + weight overflows.
inf = 10 ** 18
dist = [inf] * n
# The only distance we know for sure: the source is 0 from itself.
dist[src] = 0# Each edge is a (u, v, weight) tuple: an edge u -> v.
# bellman_ford returns shortest distances from src, or None if a negative
# cycle is reachable (then distances are undefined).
def bellman_ford(n, edges, src):
# Every node starts unreachable. inf must be large but not so large that
# inf + weight overflows.
inf = 10 ** 18
dist = [inf] * n
# The only distance we know for sure: the source is 0 from itself.
dist[src] = 0
# A shortest path visits at most n-1 edges, so n-1 rounds are enough for
# every distance to settle. (Each round may propagate one more edge.)# Each edge is a (u, v, weight) tuple: an edge u -> v.
# bellman_ford returns shortest distances from src, or None if a negative
# cycle is reachable (then distances are undefined).
def bellman_ford(n, edges, src):
# Every node starts unreachable. inf must be large but not so large that
# inf + weight overflows.
inf = 10 ** 18
dist = [inf] * n
# The only distance we know for sure: the source is 0 from itself.
dist[src] = 0
# A shortest path visits at most n-1 edges, so n-1 rounds are enough for
# every distance to settle. (Each round may propagate one more edge.)
for _ in range(n - 1):
pass# Each edge is a (u, v, weight) tuple: an edge u -> v.
# bellman_ford returns shortest distances from src, or None if a negative
# cycle is reachable (then distances are undefined).
def bellman_ford(n, edges, src):
# Every node starts unreachable. inf must be large but not so large that
# inf + weight overflows.
inf = 10 ** 18
dist = [inf] * n
# The only distance we know for sure: the source is 0 from itself.
dist[src] = 0
# A shortest path visits at most n-1 edges, so n-1 rounds are enough for
# every distance to settle. (Each round may propagate one more edge.)
for _ in range(n - 1):
# "Relax" every edge: if reaching `u` and taking this edge beats the
# best known distance to `v`, record the shorter route.
pass# Each edge is a (u, v, weight) tuple: an edge u -> v.
# bellman_ford returns shortest distances from src, or None if a negative
# cycle is reachable (then distances are undefined).
def bellman_ford(n, edges, src):
# Every node starts unreachable. inf must be large but not so large that
# inf + weight overflows.
inf = 10 ** 18
dist = [inf] * n
# The only distance we know for sure: the source is 0 from itself.
dist[src] = 0
# A shortest path visits at most n-1 edges, so n-1 rounds are enough for
# every distance to settle. (Each round may propagate one more edge.)
for _ in range(n - 1):
# "Relax" every edge: if reaching `u` and taking this edge beats the
# best known distance to `v`, record the shorter route.
for u, v, weight in edges:
if dist[u] != inf and dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight# Each edge is a (u, v, weight) tuple: an edge u -> v.
# bellman_ford returns shortest distances from src, or None if a negative
# cycle is reachable (then distances are undefined).
def bellman_ford(n, edges, src):
# Every node starts unreachable. inf must be large but not so large that
# inf + weight overflows.
inf = 10 ** 18
dist = [inf] * n
# The only distance we know for sure: the source is 0 from itself.
dist[src] = 0
# A shortest path visits at most n-1 edges, so n-1 rounds are enough for
# every distance to settle. (Each round may propagate one more edge.)
for _ in range(n - 1):
# "Relax" every edge: if reaching `u` and taking this edge beats the
# best known distance to `v`, record the shorter route.
for u, v, weight in edges:
if dist[u] != inf and dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
# After n-1 rounds distances are final — UNLESS a negative cycle exists.
# One more relaxing pass: if anything still improves, such a cycle is
# reachable and "shortest path" is undefined.# Each edge is a (u, v, weight) tuple: an edge u -> v.
# bellman_ford returns shortest distances from src, or None if a negative
# cycle is reachable (then distances are undefined).
def bellman_ford(n, edges, src):
# Every node starts unreachable. inf must be large but not so large that
# inf + weight overflows.
inf = 10 ** 18
dist = [inf] * n
# The only distance we know for sure: the source is 0 from itself.
dist[src] = 0
# A shortest path visits at most n-1 edges, so n-1 rounds are enough for
# every distance to settle. (Each round may propagate one more edge.)
for _ in range(n - 1):
# "Relax" every edge: if reaching `u` and taking this edge beats the
# best known distance to `v`, record the shorter route.
for u, v, weight in edges:
if dist[u] != inf and dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
# After n-1 rounds distances are final — UNLESS a negative cycle exists.
# One more relaxing pass: if anything still improves, such a cycle is
# reachable and "shortest path" is undefined.
for u, v, weight in edges:
if dist[u] != inf and dist[u] + weight < dist[v]:
return None
return dist # O(V * E)// Each edge is an object { from, to, weight }.
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
function bellmanFord(n, edges, src) {
}// Each edge is an object { from, to, weight }.
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
function bellmanFord(n, edges, src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight loses precision.
}// Each edge is an object { from, to, weight }.
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
function bellmanFord(n, edges, src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight loses precision.
const inf = 1e18;
const dist = new Array(n).fill(inf);
}// Each edge is an object { from, to, weight }.
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
function bellmanFord(n, edges, src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight loses precision.
const inf = 1e18;
const dist = new Array(n).fill(inf);
// The only distance we know for sure: the source is 0 from itself.
}// Each edge is an object { from, to, weight }.
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
function bellmanFord(n, edges, src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight loses precision.
const inf = 1e18;
const dist = new Array(n).fill(inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
}// Each edge is an object { from, to, weight }.
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
function bellmanFord(n, edges, src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight loses precision.
const inf = 1e18;
const dist = new Array(n).fill(inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
}// Each edge is an object { from, to, weight }.
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
function bellmanFord(n, edges, src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight loses precision.
const inf = 1e18;
const dist = new Array(n).fill(inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (let i = 0; i < n - 1; i++) {
}
}// Each edge is an object { from, to, weight }.
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
function bellmanFord(n, edges, src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight loses precision.
const inf = 1e18;
const dist = new Array(n).fill(inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (let i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
}
}// Each edge is an object { from, to, weight }.
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
function bellmanFord(n, edges, src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight loses precision.
const inf = 1e18;
const dist = new Array(n).fill(inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (let i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
for (const e of edges) {
if (dist[e.from] !== inf && dist[e.from] + e.weight < dist[e.to]) {
dist[e.to] = dist[e.from] + e.weight;
}
}
}
}// Each edge is an object { from, to, weight }.
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
function bellmanFord(n, edges, src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight loses precision.
const inf = 1e18;
const dist = new Array(n).fill(inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (let i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
for (const e of edges) {
if (dist[e.from] !== inf && dist[e.from] + e.weight < dist[e.to]) {
dist[e.to] = dist[e.from] + e.weight;
}
}
}
// After n-1 rounds distances are final — UNLESS a negative cycle exists.
// One more relaxing pass: if anything still improves, such a cycle is
// reachable and "shortest path" is undefined.
}// Each edge is an object { from, to, weight }.
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
function bellmanFord(n, edges, src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight loses precision.
const inf = 1e18;
const dist = new Array(n).fill(inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (let i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
for (const e of edges) {
if (dist[e.from] !== inf && dist[e.from] + e.weight < dist[e.to]) {
dist[e.to] = dist[e.from] + e.weight;
}
}
}
// After n-1 rounds distances are final — UNLESS a negative cycle exists.
// One more relaxing pass: if anything still improves, such a cycle is
// reachable and "shortest path" is undefined.
for (const e of edges) {
if (dist[e.from] !== inf && dist[e.from] + e.weight < dist[e.to]) {
return null;
}
}
return dist; // O(V * E)
}interface Edge {
from: number;
to: number;
weight: number;
}
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
function bellmanFord(n: number, edges: Edge[], src: number): number[] | null {
}interface Edge {
from: number;
to: number;
weight: number;
}
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
function bellmanFord(n: number, edges: Edge[], src: number): number[] | null {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight loses precision.
}interface Edge {
from: number;
to: number;
weight: number;
}
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
function bellmanFord(n: number, edges: Edge[], src: number): number[] | null {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight loses precision.
const inf = 1e18;
const dist: number[] = new Array(n).fill(inf);
}interface Edge {
from: number;
to: number;
weight: number;
}
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
function bellmanFord(n: number, edges: Edge[], src: number): number[] | null {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight loses precision.
const inf = 1e18;
const dist: number[] = new Array(n).fill(inf);
// The only distance we know for sure: the source is 0 from itself.
}interface Edge {
from: number;
to: number;
weight: number;
}
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
function bellmanFord(n: number, edges: Edge[], src: number): number[] | null {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight loses precision.
const inf = 1e18;
const dist: number[] = new Array(n).fill(inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
}interface Edge {
from: number;
to: number;
weight: number;
}
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
function bellmanFord(n: number, edges: Edge[], src: number): number[] | null {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight loses precision.
const inf = 1e18;
const dist: number[] = new Array(n).fill(inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
}interface Edge {
from: number;
to: number;
weight: number;
}
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
function bellmanFord(n: number, edges: Edge[], src: number): number[] | null {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight loses precision.
const inf = 1e18;
const dist: number[] = new Array(n).fill(inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (let i = 0; i < n - 1; i++) {
}
}interface Edge {
from: number;
to: number;
weight: number;
}
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
function bellmanFord(n: number, edges: Edge[], src: number): number[] | null {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight loses precision.
const inf = 1e18;
const dist: number[] = new Array(n).fill(inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (let i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
}
}interface Edge {
from: number;
to: number;
weight: number;
}
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
function bellmanFord(n: number, edges: Edge[], src: number): number[] | null {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight loses precision.
const inf = 1e18;
const dist: number[] = new Array(n).fill(inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (let i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
for (const e of edges) {
if (dist[e.from] !== inf && dist[e.from] + e.weight < dist[e.to]) {
dist[e.to] = dist[e.from] + e.weight;
}
}
}
}interface Edge {
from: number;
to: number;
weight: number;
}
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
function bellmanFord(n: number, edges: Edge[], src: number): number[] | null {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight loses precision.
const inf = 1e18;
const dist: number[] = new Array(n).fill(inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (let i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
for (const e of edges) {
if (dist[e.from] !== inf && dist[e.from] + e.weight < dist[e.to]) {
dist[e.to] = dist[e.from] + e.weight;
}
}
}
// After n-1 rounds distances are final — UNLESS a negative cycle exists.
// One more relaxing pass: if anything still improves, such a cycle is
// reachable and "shortest path" is undefined.
}interface Edge {
from: number;
to: number;
weight: number;
}
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
function bellmanFord(n: number, edges: Edge[], src: number): number[] | null {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight loses precision.
const inf = 1e18;
const dist: number[] = new Array(n).fill(inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (let i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
for (const e of edges) {
if (dist[e.from] !== inf && dist[e.from] + e.weight < dist[e.to]) {
dist[e.to] = dist[e.from] + e.weight;
}
}
}
// After n-1 rounds distances are final — UNLESS a negative cycle exists.
// One more relaxing pass: if anything still improves, such a cycle is
// reachable and "shortest path" is undefined.
for (const e of edges) {
if (dist[e.from] !== inf && dist[e.from] + e.weight < dist[e.to]) {
return null;
}
}
return dist; // O(V * E)
}import java.util.Arrays;
class Solution {
record Edge(int from, int to, int weight) {}
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
public long[] bellmanFord(int n, Edge[] edges, int src) {
}
}import java.util.Arrays;
class Solution {
record Edge(int from, int to, int weight) {}
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
public long[] bellmanFord(int n, Edge[] edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long.
}
}import java.util.Arrays;
class Solution {
record Edge(int from, int to, int weight) {}
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
public long[] bellmanFord(int n, Edge[] edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long.
final long inf = (long) 1e18;
long[] dist = new long[n];
Arrays.fill(dist, inf);
}
}import java.util.Arrays;
class Solution {
record Edge(int from, int to, int weight) {}
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
public long[] bellmanFord(int n, Edge[] edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long.
final long inf = (long) 1e18;
long[] dist = new long[n];
Arrays.fill(dist, inf);
// The only distance we know for sure: the source is 0 from itself.
}
}import java.util.Arrays;
class Solution {
record Edge(int from, int to, int weight) {}
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
public long[] bellmanFord(int n, Edge[] edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long.
final long inf = (long) 1e18;
long[] dist = new long[n];
Arrays.fill(dist, inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
}
}import java.util.Arrays;
class Solution {
record Edge(int from, int to, int weight) {}
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
public long[] bellmanFord(int n, Edge[] edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long.
final long inf = (long) 1e18;
long[] dist = new long[n];
Arrays.fill(dist, inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
}
}import java.util.Arrays;
class Solution {
record Edge(int from, int to, int weight) {}
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
public long[] bellmanFord(int n, Edge[] edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long.
final long inf = (long) 1e18;
long[] dist = new long[n];
Arrays.fill(dist, inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (int i = 0; i < n - 1; i++) {
}
}
}import java.util.Arrays;
class Solution {
record Edge(int from, int to, int weight) {}
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
public long[] bellmanFord(int n, Edge[] edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long.
final long inf = (long) 1e18;
long[] dist = new long[n];
Arrays.fill(dist, inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (int i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
}
}
}import java.util.Arrays;
class Solution {
record Edge(int from, int to, int weight) {}
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
public long[] bellmanFord(int n, Edge[] edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long.
final long inf = (long) 1e18;
long[] dist = new long[n];
Arrays.fill(dist, inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (int i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
for (Edge e : edges) {
if (dist[e.from()] != inf && dist[e.from()] + e.weight() < dist[e.to()]) {
dist[e.to()] = dist[e.from()] + e.weight();
}
}
}
}
}import java.util.Arrays;
class Solution {
record Edge(int from, int to, int weight) {}
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
public long[] bellmanFord(int n, Edge[] edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long.
final long inf = (long) 1e18;
long[] dist = new long[n];
Arrays.fill(dist, inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (int i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
for (Edge e : edges) {
if (dist[e.from()] != inf && dist[e.from()] + e.weight() < dist[e.to()]) {
dist[e.to()] = dist[e.from()] + e.weight();
}
}
}
// After n-1 rounds distances are final — UNLESS a negative cycle exists.
// One more relaxing pass: if anything still improves, such a cycle is
// reachable and "shortest path" is undefined.
}
}import java.util.Arrays;
class Solution {
record Edge(int from, int to, int weight) {}
// bellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
public long[] bellmanFord(int n, Edge[] edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long.
final long inf = (long) 1e18;
long[] dist = new long[n];
Arrays.fill(dist, inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (int i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
for (Edge e : edges) {
if (dist[e.from()] != inf && dist[e.from()] + e.weight() < dist[e.to()]) {
dist[e.to()] = dist[e.from()] + e.weight();
}
}
}
// After n-1 rounds distances are final — UNLESS a negative cycle exists.
// One more relaxing pass: if anything still improves, such a cycle is
// reachable and "shortest path" is undefined.
for (Edge e : edges) {
if (dist[e.from()] != inf && dist[e.from()] + e.weight() < dist[e.to()]) {
return null;
}
}
return dist; // O(V * E)
}
}using System;
public class Solution {
public record Edge(int From, int To, int Weight);
// BellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
public long[] BellmanFord(int n, Edge[] edges, int src) {
}
}using System;
public class Solution {
public record Edge(int From, int To, int Weight);
// BellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
public long[] BellmanFord(int n, Edge[] edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long.
}
}using System;
public class Solution {
public record Edge(int From, int To, int Weight);
// BellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
public long[] BellmanFord(int n, Edge[] edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long.
const long inf = 1000000000000000000L;
long[] dist = new long[n];
Array.Fill(dist, inf);
}
}using System;
public class Solution {
public record Edge(int From, int To, int Weight);
// BellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
public long[] BellmanFord(int n, Edge[] edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long.
const long inf = 1000000000000000000L;
long[] dist = new long[n];
Array.Fill(dist, inf);
// The only distance we know for sure: the source is 0 from itself.
}
}using System;
public class Solution {
public record Edge(int From, int To, int Weight);
// BellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
public long[] BellmanFord(int n, Edge[] edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long.
const long inf = 1000000000000000000L;
long[] dist = new long[n];
Array.Fill(dist, inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
}
}using System;
public class Solution {
public record Edge(int From, int To, int Weight);
// BellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
public long[] BellmanFord(int n, Edge[] edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long.
const long inf = 1000000000000000000L;
long[] dist = new long[n];
Array.Fill(dist, inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
}
}using System;
public class Solution {
public record Edge(int From, int To, int Weight);
// BellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
public long[] BellmanFord(int n, Edge[] edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long.
const long inf = 1000000000000000000L;
long[] dist = new long[n];
Array.Fill(dist, inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (int i = 0; i < n - 1; i++) {
}
}
}using System;
public class Solution {
public record Edge(int From, int To, int Weight);
// BellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
public long[] BellmanFord(int n, Edge[] edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long.
const long inf = 1000000000000000000L;
long[] dist = new long[n];
Array.Fill(dist, inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (int i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `From` and taking this edge beats the
// best known distance to `To`, record the shorter route.
}
}
}using System;
public class Solution {
public record Edge(int From, int To, int Weight);
// BellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
public long[] BellmanFord(int n, Edge[] edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long.
const long inf = 1000000000000000000L;
long[] dist = new long[n];
Array.Fill(dist, inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (int i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `From` and taking this edge beats the
// best known distance to `To`, record the shorter route.
foreach (Edge e in edges) {
if (dist[e.From] != inf && dist[e.From] + e.Weight < dist[e.To]) {
dist[e.To] = dist[e.From] + e.Weight;
}
}
}
}
}using System;
public class Solution {
public record Edge(int From, int To, int Weight);
// BellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
public long[] BellmanFord(int n, Edge[] edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long.
const long inf = 1000000000000000000L;
long[] dist = new long[n];
Array.Fill(dist, inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (int i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `From` and taking this edge beats the
// best known distance to `To`, record the shorter route.
foreach (Edge e in edges) {
if (dist[e.From] != inf && dist[e.From] + e.Weight < dist[e.To]) {
dist[e.To] = dist[e.From] + e.Weight;
}
}
}
// After n-1 rounds distances are final — UNLESS a negative cycle exists.
// One more relaxing pass: if anything still improves, such a cycle is
// reachable and "shortest path" is undefined.
}
}using System;
public class Solution {
public record Edge(int From, int To, int Weight);
// BellmanFord returns shortest distances from src, or null if a negative
// cycle is reachable (then distances are undefined).
public long[] BellmanFord(int n, Edge[] edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long.
const long inf = 1000000000000000000L;
long[] dist = new long[n];
Array.Fill(dist, inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (int i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `From` and taking this edge beats the
// best known distance to `To`, record the shorter route.
foreach (Edge e in edges) {
if (dist[e.From] != inf && dist[e.From] + e.Weight < dist[e.To]) {
dist[e.To] = dist[e.From] + e.Weight;
}
}
}
// After n-1 rounds distances are final — UNLESS a negative cycle exists.
// One more relaxing pass: if anything still improves, such a cycle is
// reachable and "shortest path" is undefined.
foreach (Edge e in edges) {
if (dist[e.From] != inf && dist[e.From] + e.Weight < dist[e.To]) {
return null;
}
}
return dist; // O(V * E)
}
}#include <stdbool.h>
typedef struct {
int from, to, weight;
} Edge;
// bellmanFord fills dist[0..n) with shortest distances from src and returns
// true. It returns false if a negative cycle is reachable (dist is then
// undefined). The caller owns dist.
bool bellmanFord(int n, Edge* edges, int edgesSize, int src, long long* dist) {
}#include <stdbool.h>
typedef struct {
int from, to, weight;
} Edge;
// bellmanFord fills dist[0..n) with shortest distances from src and returns
// true. It returns false if a negative cycle is reachable (dist is then
// undefined). The caller owns dist.
bool bellmanFord(int n, Edge* edges, int edgesSize, int src, long long* dist) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long long.
}#include <stdbool.h>
typedef struct {
int from, to, weight;
} Edge;
// bellmanFord fills dist[0..n) with shortest distances from src and returns
// true. It returns false if a negative cycle is reachable (dist is then
// undefined). The caller owns dist.
bool bellmanFord(int n, Edge* edges, int edgesSize, int src, long long* dist) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long long.
const long long inf = 1000000000000000000LL;
for (int i = 0; i < n; i++) {
dist[i] = inf;
}
}#include <stdbool.h>
typedef struct {
int from, to, weight;
} Edge;
// bellmanFord fills dist[0..n) with shortest distances from src and returns
// true. It returns false if a negative cycle is reachable (dist is then
// undefined). The caller owns dist.
bool bellmanFord(int n, Edge* edges, int edgesSize, int src, long long* dist) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long long.
const long long inf = 1000000000000000000LL;
for (int i = 0; i < n; i++) {
dist[i] = inf;
}
// The only distance we know for sure: the source is 0 from itself.
}#include <stdbool.h>
typedef struct {
int from, to, weight;
} Edge;
// bellmanFord fills dist[0..n) with shortest distances from src and returns
// true. It returns false if a negative cycle is reachable (dist is then
// undefined). The caller owns dist.
bool bellmanFord(int n, Edge* edges, int edgesSize, int src, long long* dist) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long long.
const long long inf = 1000000000000000000LL;
for (int i = 0; i < n; i++) {
dist[i] = inf;
}
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
}#include <stdbool.h>
typedef struct {
int from, to, weight;
} Edge;
// bellmanFord fills dist[0..n) with shortest distances from src and returns
// true. It returns false if a negative cycle is reachable (dist is then
// undefined). The caller owns dist.
bool bellmanFord(int n, Edge* edges, int edgesSize, int src, long long* dist) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long long.
const long long inf = 1000000000000000000LL;
for (int i = 0; i < n; i++) {
dist[i] = inf;
}
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
}#include <stdbool.h>
typedef struct {
int from, to, weight;
} Edge;
// bellmanFord fills dist[0..n) with shortest distances from src and returns
// true. It returns false if a negative cycle is reachable (dist is then
// undefined). The caller owns dist.
bool bellmanFord(int n, Edge* edges, int edgesSize, int src, long long* dist) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long long.
const long long inf = 1000000000000000000LL;
for (int i = 0; i < n; i++) {
dist[i] = inf;
}
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (int i = 0; i < n - 1; i++) {
}
}#include <stdbool.h>
typedef struct {
int from, to, weight;
} Edge;
// bellmanFord fills dist[0..n) with shortest distances from src and returns
// true. It returns false if a negative cycle is reachable (dist is then
// undefined). The caller owns dist.
bool bellmanFord(int n, Edge* edges, int edgesSize, int src, long long* dist) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long long.
const long long inf = 1000000000000000000LL;
for (int i = 0; i < n; i++) {
dist[i] = inf;
}
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (int i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
}
}#include <stdbool.h>
typedef struct {
int from, to, weight;
} Edge;
// bellmanFord fills dist[0..n) with shortest distances from src and returns
// true. It returns false if a negative cycle is reachable (dist is then
// undefined). The caller owns dist.
bool bellmanFord(int n, Edge* edges, int edgesSize, int src, long long* dist) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long long.
const long long inf = 1000000000000000000LL;
for (int i = 0; i < n; i++) {
dist[i] = inf;
}
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (int i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
for (int k = 0; k < edgesSize; k++) {
Edge e = edges[k];
if (dist[e.from] != inf && dist[e.from] + e.weight < dist[e.to]) {
dist[e.to] = dist[e.from] + e.weight;
}
}
}
}#include <stdbool.h>
typedef struct {
int from, to, weight;
} Edge;
// bellmanFord fills dist[0..n) with shortest distances from src and returns
// true. It returns false if a negative cycle is reachable (dist is then
// undefined). The caller owns dist.
bool bellmanFord(int n, Edge* edges, int edgesSize, int src, long long* dist) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long long.
const long long inf = 1000000000000000000LL;
for (int i = 0; i < n; i++) {
dist[i] = inf;
}
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (int i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
for (int k = 0; k < edgesSize; k++) {
Edge e = edges[k];
if (dist[e.from] != inf && dist[e.from] + e.weight < dist[e.to]) {
dist[e.to] = dist[e.from] + e.weight;
}
}
}
// After n-1 rounds distances are final — UNLESS a negative cycle exists.
// One more relaxing pass: if anything still improves, such a cycle is
// reachable and "shortest path" is undefined.
}#include <stdbool.h>
typedef struct {
int from, to, weight;
} Edge;
// bellmanFord fills dist[0..n) with shortest distances from src and returns
// true. It returns false if a negative cycle is reachable (dist is then
// undefined). The caller owns dist.
bool bellmanFord(int n, Edge* edges, int edgesSize, int src, long long* dist) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long long.
const long long inf = 1000000000000000000LL;
for (int i = 0; i < n; i++) {
dist[i] = inf;
}
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (int i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
for (int k = 0; k < edgesSize; k++) {
Edge e = edges[k];
if (dist[e.from] != inf && dist[e.from] + e.weight < dist[e.to]) {
dist[e.to] = dist[e.from] + e.weight;
}
}
}
// After n-1 rounds distances are final — UNLESS a negative cycle exists.
// One more relaxing pass: if anything still improves, such a cycle is
// reachable and "shortest path" is undefined.
for (int k = 0; k < edgesSize; k++) {
Edge e = edges[k];
if (dist[e.from] != inf && dist[e.from] + e.weight < dist[e.to]) {
return false;
}
}
return true; // O(V * E)
}#include <vector>
using namespace std;
struct Edge {
int from, to, weight;
};
class Solution {
public:
// bellmanFord returns shortest distances from src, or an empty vector if a
// negative cycle is reachable (then distances are undefined).
vector<long long> bellmanFord(int n, vector<Edge>& edges, int src) {
}
};#include <vector>
using namespace std;
struct Edge {
int from, to, weight;
};
class Solution {
public:
// bellmanFord returns shortest distances from src, or an empty vector if a
// negative cycle is reachable (then distances are undefined).
vector<long long> bellmanFord(int n, vector<Edge>& edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long long.
}
};#include <vector>
using namespace std;
struct Edge {
int from, to, weight;
};
class Solution {
public:
// bellmanFord returns shortest distances from src, or an empty vector if a
// negative cycle is reachable (then distances are undefined).
vector<long long> bellmanFord(int n, vector<Edge>& edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long long.
const long long inf = 1000000000000000000LL;
vector<long long> dist(n, inf);
}
};#include <vector>
using namespace std;
struct Edge {
int from, to, weight;
};
class Solution {
public:
// bellmanFord returns shortest distances from src, or an empty vector if a
// negative cycle is reachable (then distances are undefined).
vector<long long> bellmanFord(int n, vector<Edge>& edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long long.
const long long inf = 1000000000000000000LL;
vector<long long> dist(n, inf);
// The only distance we know for sure: the source is 0 from itself.
}
};#include <vector>
using namespace std;
struct Edge {
int from, to, weight;
};
class Solution {
public:
// bellmanFord returns shortest distances from src, or an empty vector if a
// negative cycle is reachable (then distances are undefined).
vector<long long> bellmanFord(int n, vector<Edge>& edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long long.
const long long inf = 1000000000000000000LL;
vector<long long> dist(n, inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
}
};#include <vector>
using namespace std;
struct Edge {
int from, to, weight;
};
class Solution {
public:
// bellmanFord returns shortest distances from src, or an empty vector if a
// negative cycle is reachable (then distances are undefined).
vector<long long> bellmanFord(int n, vector<Edge>& edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long long.
const long long inf = 1000000000000000000LL;
vector<long long> dist(n, inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
}
};#include <vector>
using namespace std;
struct Edge {
int from, to, weight;
};
class Solution {
public:
// bellmanFord returns shortest distances from src, or an empty vector if a
// negative cycle is reachable (then distances are undefined).
vector<long long> bellmanFord(int n, vector<Edge>& edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long long.
const long long inf = 1000000000000000000LL;
vector<long long> dist(n, inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (int i = 0; i < n - 1; i++) {
}
}
};#include <vector>
using namespace std;
struct Edge {
int from, to, weight;
};
class Solution {
public:
// bellmanFord returns shortest distances from src, or an empty vector if a
// negative cycle is reachable (then distances are undefined).
vector<long long> bellmanFord(int n, vector<Edge>& edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long long.
const long long inf = 1000000000000000000LL;
vector<long long> dist(n, inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (int i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
}
}
};#include <vector>
using namespace std;
struct Edge {
int from, to, weight;
};
class Solution {
public:
// bellmanFord returns shortest distances from src, or an empty vector if a
// negative cycle is reachable (then distances are undefined).
vector<long long> bellmanFord(int n, vector<Edge>& edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long long.
const long long inf = 1000000000000000000LL;
vector<long long> dist(n, inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (int i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
for (const Edge& e : edges) {
if (dist[e.from] != inf && dist[e.from] + e.weight < dist[e.to]) {
dist[e.to] = dist[e.from] + e.weight;
}
}
}
}
};#include <vector>
using namespace std;
struct Edge {
int from, to, weight;
};
class Solution {
public:
// bellmanFord returns shortest distances from src, or an empty vector if a
// negative cycle is reachable (then distances are undefined).
vector<long long> bellmanFord(int n, vector<Edge>& edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long long.
const long long inf = 1000000000000000000LL;
vector<long long> dist(n, inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (int i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
for (const Edge& e : edges) {
if (dist[e.from] != inf && dist[e.from] + e.weight < dist[e.to]) {
dist[e.to] = dist[e.from] + e.weight;
}
}
}
// After n-1 rounds distances are final — UNLESS a negative cycle exists.
// One more relaxing pass: if anything still improves, such a cycle is
// reachable and "shortest path" is undefined.
}
};#include <vector>
using namespace std;
struct Edge {
int from, to, weight;
};
class Solution {
public:
// bellmanFord returns shortest distances from src, or an empty vector if a
// negative cycle is reachable (then distances are undefined).
vector<long long> bellmanFord(int n, vector<Edge>& edges, int src) {
// Every node starts unreachable. inf must be large but not so large that
// inf + weight overflows a long long.
const long long inf = 1000000000000000000LL;
vector<long long> dist(n, inf);
// The only distance we know for sure: the source is 0 from itself.
dist[src] = 0;
// A shortest path visits at most n-1 edges, so n-1 rounds are enough for
// every distance to settle. (Each round may propagate one more edge.)
for (int i = 0; i < n - 1; i++) {
// "Relax" every edge: if reaching `from` and taking this edge beats the
// best known distance to `to`, record the shorter route.
for (const Edge& e : edges) {
if (dist[e.from] != inf && dist[e.from] + e.weight < dist[e.to]) {
dist[e.to] = dist[e.from] + e.weight;
}
}
}
// After n-1 rounds distances are final — UNLESS a negative cycle exists.
// One more relaxing pass: if anything still improves, such a cycle is
// reachable and "shortest path" is undefined.
for (const Edge& e : edges) {
if (dist[e.from] != inf && dist[e.from] + e.weight < dist[e.to]) {
return {};
}
}
return dist; // O(V * E)
}
};Tap the left half to go back, the right half to go forward.
Arrow keys or space to navigate · Esc to exit.