export const floydWarshall: {
  <E>(
    cost: (edgeData: E) => number
  ): <N, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>) => AllPairsResult<E>
  <N, E, T extends Kind = "directed">(
    graph: Graph<N, E, T> | MutableGraph<N, E, T>,
    cost: (edgeData: E) => number
  ): AllPairsResult<E>
} = dual(2, <N, E, T extends Kind = "directed">(
  graph: Graph<N, E, T> | MutableGraph<N, E, T>,
  cost: (edgeData: E) => number
): AllPairsResult<E> => {
  // Get all nodes for Floyd-Warshall algorithm (needs array for nested iteration)
  const allNodes = Array.from(graph.nodes.keys())

  // Initialize distance matrix
  const distances = new Map<NodeIndex, Map<NodeIndex, number>>()
  const next = new Map<NodeIndex, Map<NodeIndex, NodeIndex | null>>()
  const edgeMatrix = new Map<NodeIndex, Map<NodeIndex, E | null>>()

  // Initialize with infinity for all pairs
  for (const i of allNodes) {
    distances.set(i, new Map())
    next.set(i, new Map())
    edgeMatrix.set(i, new Map())

    for (const j of allNodes) {
      distances.get(i)!.set(j, i === j ? 0 : Infinity)
      next.get(i)!.set(j, null)
      edgeMatrix.get(i)!.set(j, null)
    }
  }

  // Set edge weights
  for (const [, edgeData] of graph.edges) {
    const weight = cost(edgeData.data)
    const i = edgeData.source
    const j = edgeData.target

    // Use minimum weight if multiple edges exist
    const currentWeight = distances.get(i)!.get(j)!
    if (weight < currentWeight) {
      distances.get(i)!.set(j, weight)
      next.get(i)!.set(j, j)
      edgeMatrix.get(i)!.set(j, edgeData.data)
    }

    if (graph.type === "undirected") {
      const reverseWeight = distances.get(j)!.get(i)!
      if (weight < reverseWeight) {
        distances.get(j)!.set(i, weight)
        next.get(j)!.set(i, i)
        edgeMatrix.get(j)!.set(i, edgeData.data)
      }
    }
  }

  // Floyd-Warshall main loop
  for (const k of allNodes) {
    for (const i of allNodes) {
      for (const j of allNodes) {
        const distIK = distances.get(i)!.get(k)!
        const distKJ = distances.get(k)!.get(j)!
        const distIJ = distances.get(i)!.get(j)!

        if (distIK !== Infinity && distKJ !== Infinity && distIK + distKJ < distIJ) {
          distances.get(i)!.set(j, distIK + distKJ)
          next.get(i)!.set(j, next.get(i)!.get(k)!)
        }
      }
    }
  }

  // Check for negative cycles
  for (const i of allNodes) {
    if (distances.get(i)!.get(i)! < 0) {
      throw new GraphError({ message: `Negative cycle detected involving node ${i}` })
    }
  }

  // Build result paths and edge weights
  const paths = new Map<NodeIndex, Map<NodeIndex, Array<NodeIndex> | null>>()
  const costs = new Map<NodeIndex, Map<NodeIndex, Array<E>>>()

  for (const i of allNodes) {
    paths.set(i, new Map())
    costs.set(i, new Map())

    for (const j of allNodes) {
      if (i === j) {
        paths.get(i)!.set(j, [i])
        costs.get(i)!.set(j, [])
      } else if (distances.get(i)!.get(j)! === Infinity) {
        paths.get(i)!.set(j, null)
        costs.get(i)!.set(j, [])
      } else {
        // Reconstruct path iteratively
        const path: Array<NodeIndex> = []
        const weights: Array<E> = []
        let current = i

        path.push(current)
        while (current !== j) {
          const nextNode = next.get(current)!.get(j)!
          if (nextNode === null) break

          const edgeData = edgeMatrix.get(current)!.get(nextNode)!
          if (edgeData !== null) {
            weights.push(edgeData)
          }

          current = nextNode
          path.push(current)
        }

        paths.get(i)!.set(j, path)
        costs.get(i)!.set(j, weights)
      }
    }
  }

  return {
    distances,
    paths,
    costs
  }
})