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

  // Early return if source equals target
  if (config.source === config.target) {
    return Option.some({
      path: [config.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 === config.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 = config.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) {
      const sourceDistance = distances.get(edge.source)!
      const targetDistance = distances.get(edge.target)!

      // Relaxation step
      if (sourceDistance !== Infinity && sourceDistance + edge.weight < targetDistance) {
        distances.set(edge.target, sourceDistance + edge.weight)
        previous.set(edge.target, { node: edge.source, edgeData: edge.edgeData })
        hasUpdate = true
      }
    }

    // Early termination if no updates
    if (!hasUpdate) {
      break
    }
  }

  // Check for negative cycles
  for (const edge of edges) {
    const sourceDistance = distances.get(edge.source)!
    const targetDistance = distances.get(edge.target)!

    if (sourceDistance !== Infinity && sourceDistance + edge.weight < targetDistance) {
      // Negative cycle detected - check if it affects the path to target
      const affectedNodes = new Set<NodeIndex>()
      const queue = [edge.target]

      while (queue.length > 0) {
        const node = queue.shift()!
        if (affectedNodes.has(node)) continue
        affectedNodes.add(node)

        // Add all nodes reachable from this node
        for (const neighbor of getTraversalNeighbors(graph, node, "outgoing")) {
          queue.push(neighbor)
        }
      }

      // If target is affected by a negative cycle, no shortest path exists.
      if (affectedNodes.has(config.target)) {
        return Option.none()
      }
    }
  }

  // Check if target is reachable
  const distance = distances.get(config.target)!
  if (distance === Infinity) {
    return Option.none() // No path exists
  }

  // Reconstruct path
  const path: Array<NodeIndex> = []
  const costs: Array<E> = []
  let currentNode: NodeIndex | null = config.target

  while (currentNode !== null) {
    path.unshift(currentNode)
    const prev: { node: NodeIndex; edgeData: E } | null = previous.get(currentNode)!
    if (prev !== null) {
      costs.unshift(prev.edgeData)
      currentNode = prev.node
    } else {
      currentNode = null
    }
  }

  return Option.some({
    path,
    distance,
    costs
  })
})