Function bellmanFord

packages/effect/src/Graph.ts:2880–3010

(
  graph: Graph<N, E, T> | MutableGraph<N, E, T>,
  config: BellmanFordConfig<E>
)

 * @category algorithms
 */
export const bellmanFord = <N, E, T extends Kind = "directed">(
  graph: Graph<N, E, T> | MutableGraph<N, E, T>,
  config: BellmanFordConfig<E>
): Option.Option<PathResult<E>> => {
  const { cost, source, target } = config
  // Validate that source and target nodes exist
  if (!graph.nodes.has(source)) {
    throw missingNode(source)
  }
  if (!graph.nodes.has(target)) {
    throw missingNode(target)
  }

  // Early return if source equals target
  if (source === target) {
    return Option.some({
      path: [source],
      distance: 0,
      costs: []
    })
  }

  // Initialize distances and predecessors
  const distances = new Map<NodeIndex, number>()
  const previous = new Map<NodeIndex, { node: NodeIndex; edgeData: E } | null>()
  // Iterate directly over node keys

  for (const node of graph.nodes.keys()) {
    distances.set(node, node === source ? 0 : Infinity)
    previous.set(node, null)
  }

  // Collect all edges for relaxation
  const edges: Array<{ source: NodeIndex; target: NodeIndex; weight: number; edgeData: E }> = []
  for (const [, edgeData] of graph.edges) {
    const weight = cost(edgeData.data)
    edges.push({
      source: edgeData.source,
      target: edgeData.target,
      weight,
      edgeData: edgeData.data
    })
    if (graph.type === "undirected" && edgeData.source !== edgeData.target) {
      edges.push({
        source: edgeData.target,
        target: edgeData.source,
        weight,
        edgeData: edgeData.data
      })
    }
  }

  // Relax edges up to V-1 times
  const nodeCount = graph.nodes.size
  for (let i = 0; i < nodeCount - 1; i++) {
    let hasUpdate = false

    for (const edge of edges) {