Rafael Romão's Coding Labs

Lab L21 · Java + Go

Implementing a route planner

Build a shortest-path finder for a directed graph with non-negative edge costs: return the cheapest node sequence from start to goal and its total cost. Implement Dijkstra first; then accept an optional heuristic h(node), a never-too-high estimate of the remaining cost, which turns the same loop into A*. The extension, TurnPlanner, supports forbidden turns (“no left from road X onto road Y”) by searching over roads instead of junctions.

The task

Routing a driver from pickup to drop-off: junctions are nodes, road segments are directed edges, costs are seconds of travel. Dijkstra explores outward by cost; A* uses a heuristic such as straight-line distance divided by maximum speed to explore toward the goal first, and stays correct as long as the heuristic never overestimates. A turn ban cannot be expressed on junctions alone, because whether you may take road Y depends on which road you arrived by, so the state becomes “the road I am on”.

14115ABCD✗ no AB → BCDijkstra / A*:A → B → C → D, cost 3turn AB → BC blocked:AC, CD cost 5(AB, BD would cost 6)turn bans need state = incoming road, not just the junction
The cheapest route takes the long-looking way round (cost 3 against the direct 5 via B→D). Blocking the turn from AB onto BC at B forces the planner to compare the two remaining routes.

What you implement

public final class RoutePlanner {
    public record Edge(String to, double cost) {}
    public record Route(List<String> nodes, double cost, boolean found) {}
    public static Route find(Map<String, List<Edge>> graph, String start, String goal,
                             ToDoubleFunction<String> heuristic);   // null -> Dijkstra
}

public final class TurnPlanner {                                    // extension
    public record Road(String id, String from, String to, double cost) {}
    public record Turn(String incoming, String outgoing) {}         // road id -> road id
    public static RoutePlanner.Route find(List<Road> roads, Set<Turn> blocked,
                                          String start, String goal);   // nodes = road ids
}

Rules

  • Validation → IllegalArgumentException: start or goal not a key of the graph; an edge to an undeclared node; a negative, NaN or infinite cost; a heuristic value that is negative or non-finite; h(goal) != 0.
  • Unreachable goal → Route([], 0, false). start == goal → Route([start], 0, true).
  • The route lists every node from start to goal inclusive; rebuild it from a previous map.
  • Priority queue ordered by cost + h(node) (ties by node name). Skip queue entries whose cost is no longer the best known (lazy deletion).
  • TurnPlanner: you may go from road a to road b when a.to == b.from and (a, b) is not blocked. Duplicate road ids, or a blocked turn naming unknown or unconnected roads → IllegalArgumentException. The result lists road ids.

Worked example

  1. Edges: A→B 1, A→C 4, B→C 1, C→D 1, B→D 5.
  2. find(A, D, null) → [A, B, C, D], cost 3. With an admissible heuristic: same route, usually fewer nodes expanded.
  3. As roads AB, AC, BC, CD, BD with turn AB → BC blocked: [AC, CD] cost 5 beats [AB, BD] cost 6.

Files and commands

Read the tests first, then replace each TODO in the starter until they pass. Java starter: RoutePlanner.java, TurnPlanner.java · tests: RoutePlannerTest.java, TurnPlannerTest.java. Go starter: planner.go, turns.go · tests: planner_test.go, turns_test.go.

cd java
./gradlew test --tests 'labs.routing.*'

cd go
go test -race -count=1 ./routing
Reveal the reference solutions

Java: RoutePlanner.java, TurnPlanner.java
Go: planner.go, turns.go

When to use

Use this lab to find a minimum-cost route through a directed graph. Edge costs must be finite and nonnegative, and all destinations must be declared nodes. Costs have caller-selected units: distance, elapsed time, or another additive measure. Graphs must remain unchanged during the call; callers should pass a snapshot rather than allowing live edits. The result separates no route from a zero-cost route. Both Java and Go implementations return the route's node sequence and accumulated cost.

This is a graph-search core, not a road-routing product. There is no geocoding, map matching, turn-restriction parser, live traffic integration, or graph-size quota. Those concerns change the state model and must be added explicitly. Turn restrictions, for example, require state that includes the incoming edge rather than only the current junction.

Steps

  1. Establish the reference search. With no heuristic, the implementation uses Dijkstra's algorithm. Store the best known cost per node and a predecessor for path reconstruction. A min-priority queue chooses the next candidate.
  2. Handle improving candidates. Relax an outgoing edge only if it improves the destination's recorded cost. Queue a new candidate and ignore obsolete candidates when popped. Do not mark a node permanently visited on insertion: a cheaper route can appear later.
  3. Add a heuristic contract. A* orders candidates by accumulated cost plus estimated remaining cost. Estimates must be finite, nonnegative, zero at the goal, and admissible: never greater than the true cheapest remaining cost. The code validates numeric properties, not admissibility, which is the caller's proof obligation. Nodes can reopen after improvements, allowing admissible but inconsistent estimates.
  4. Choose the right units. Straight-line distance may be an admissible lower bound for distance costs, but not directly for seconds. A travel-time heuristic needs a defensible speed bound and the same cost units. Zero is always a safe lower bound when costs are nonnegative, reducing A* to Dijkstra.
  5. Recover and test the route. In a graph where A-to-B costs four but A-to-C-to-B costs two, verify that a later improvement replaces B's predecessor. Compare Dijkstra with an admissible A* heuristic, check disconnected nodes, and check start equal to goal. Reject negative, infinite, and NaN edge costs and reject arithmetic overflow.
  6. Explain cost and determinism. Dijkstra with duplicate heap entries typically uses O((V+E) log E) work and O(V+E) memory. Inconsistent A* heuristics can cause repeated expansions and worse work. Equal-priority nodes use their names as a tie-break, but equal-cost alternative paths can still depend on adjacency order. Floating-point results are not exact real arithmetic; strict accounting may require checked integral costs.

Checklist

Turn-dependent extension and recall

Rebuild relaxation before reading Go or Java. The paired TurnPlanner/FindWithTurns extension searches incoming-road states and rejects named forbidden turns, using zero heuristic. Its test requires reaching the same junction through a different road before taking the exit. Returned nodes are road identities for this variant. Transition expansion is quadratic in the supplied road count and is a teaching representation, not a continental road index.

Variation: add a cheaper forbidden approach. Acceptance: the route still honors the restriction rather than marking the junction permanently visited after the cheapest arrival.

  • Graph and weight snapshot do not change mid-search
  • All edge costs and heuristic values meet the numeric contract
  • Heuristic admissibility is justified for the actual cost function
  • Stale queue entries are skipped and improved nodes can reopen
  • No-route and zero-cost-route outcomes remain distinct

Signals

Working: reconstructed edges exist, their costs agree with the reported cost, and A* agrees with the zero-heuristic reference on test graphs.

Going wrong: geographic distance is used directly as a time heuristic, edges change mid-query, or the implementation stops when the goal is first discovered rather than when its best candidate is selected under the stated assumptions.

Related