Function dijkstra

packages/effect/src/Graph.ts:2380–2505

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

 * @category algorithms
 */
export const dijkstra = <N, E, T extends Kind = "directed">(
  graph: Graph<N, E, T> | MutableGraph<N, E, T>,
  config: DijkstraConfig<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: []
    })
  }

  // 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 === 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: 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)