weightedShortestPath

Weighted shortest path from from to to, respecting edge weights. Returns the path (including both endpoints) plus total weighted cost. Returns null if to is not reachable. A self-path (from === to) returns WeightedPath(listOf(from), 0.0).

Edge weights must be non-negative. No runtime check (would be O(E)); negative weights cause incorrect results.

Mode of operation, controlled by the heuristic parameter:

• Dijkstra (default): pass no heuristic, or pass { _, _ -> 0.0 }. The algorithm explores nodes in order of g(n) — actual cost from from to n. Optimal, but uninformed: it may explore many irrelevant nodes when the target is in a specific direction.

• **A\***: pass a non-trivial heuristic (currentNode, targetNode) -> Double that estimates the cost from currentNode to targetNode. The algorithm explores nodes in order of f(n) = g(n) + h(n, to). If the heuristic is admissible (never overestimates actual cost), A\* finds the optimal path while exploring far fewer nodes than Dijkstra in practice.

Admissibility of a heuristic is not enforced at runtime. Common admissible heuristics:

• Geometric distance (straight-line) when nodes have positions and edges follow physical paths whose weights are at least the geometric distance. The natural pattern for combining this with a ContinuousProjection:

    net.weightedShortestPath(start, dest) { a, b ->
        space.distance(space.positionOf(a)!!, space.positionOf(b)!!)
    }

  Content copied to clipboard

• Zero — always admissible; equivalent to Dijkstra.

An inadmissible heuristic may produce a sub-optimal path; the algorithm will still terminate and return some path if reachable.

Complexity: O((V + E) log V) with the binary-heap priority queue used here. Early-exit when the target is finalized reduces practical cost significantly when the target is close to the source relative to the graph diameter.