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)
}Tap the left half to go back, the right half to go forward.
Arrow keys or space to navigate · Esc to exit.