export const dijkstra: {
  <E>(
    config: DijkstraConfig<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: DijkstraConfig<E>
  ): Option.Option<PathResult<E>>
} = dual(2, <N, E, T extends Kind = "directed">(
  graph: Graph<N, E, T> | MutableGraph<N, E, T>,
  config: DijkstraConfig<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)
  }

  const edgeWeights = validateNonNegativeEdgeWeights(graph, config.cost, "Dijkstra's algorithm")

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

  // Distance tracking and priority queue simulation
  const distances = new Map<NodeIndex, number>()
  const previous = new Map<NodeIndex, { node: NodeIndex; edgeData: E } | null>()
  const visited = new Set<NodeIndex>()

  // Initialize distances
  // Iterate directly over node keys
  for (const node of graph.nodes.keys()) {
    distances.set(node, node === config.source ? 0 : Infinity)
    previous.set(node, null)
  }

  // Simple priority queue using array (can be optimized with proper heap)
  const priorityQueue: Array<{ node: NodeIndex; distance: number }> = [
    { node: config.source, distance: 0 }
  ]

  while (priorityQueue.length > 0) {
    // Find minimum distance node (priority queue extract-min)
    let minIndex = 0
    for (let i = 1; i < priorityQueue.length; i++) {
      if (priorityQueue[i].distance < priorityQueue[minIndex].distance) {
        minIndex = i
      }
    }

    const current = priorityQueue.splice(minIndex, 1)[0]
    const currentNode = current.node

    // Skip if already visited (can happen with duplicate entries)
    if (visited.has(currentNode)) {
      continue
    }

    visited.add(currentNode)

    // Early termination if we reached the target
    if (currentNode === config.target) {
      break
    }

    // Get current distance
    const currentDistance = distances.get(currentNode)!

    // Examine all outgoing edges
    const adjacencyList = graph.adjacency.get(currentNode)
    if (adjacencyList !== undefined) {
      for (const edgeIndex of adjacencyList) {
        const edge = graph.edges.get(edgeIndex)
        if (edge !== undefined) {
          const neighbor = getTraversableNeighbor(graph, currentNode, edge)
          const cost = edgeWeights.get(edgeIndex)!

          const newDistance = currentDistance + cost
          const neighborDistance = distances.get(neighbor)!

          // Relaxation step
          if (newDistance < neighborDistance) {
            distances.set(neighbor, newDistance)
            previous.set(neighbor, { node: currentNode, edgeData: edge.data })

            // Add to priority queue if not visited
            if (!visited.has(neighbor)) {
              priorityQueue.push({ node: neighbor, distance: newDistance })
            }
          }
        }
      }
    }
  }

  // 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
  })
})