Building Roadrunner, A Correct Dijkstra Baseline in Rust

The Brief

Roadrunner is a routing and delivery optimization engine I am building from the ground up. Before it can assign riders, estimate arrival times, or react to traffic, it needs to answer a smaller question correctly:

What is the cheapest path from one node in a road graph to another?

Phase 5 was about building that baseline with Dijkstra's shortest-path algorithm. I implemented it manually in Rust instead of calling a library function because the routing algorithm is core Roadrunner behavior. I wanted its decisions, failure cases, and performance to remain visible.

The goal was not to make the fastest router immediately. The goal was to build one that was correct, tested, measurable, and useful as a reference for later algorithms such as A*.

Dijkstra in Plain English

Imagine every road junction is a node and every one-way road is an edge with a cost.

Dijkstra starts at the source with a cost of zero. It repeatedly visits the cheapest unvisited node, checks whether travelling through that node improves the known cost of its neighbours, and records each improvement. Once the destination becomes the cheapest node in the queue, its best route is known.

The loop can be reduced to this:

put the source in the queue with cost 0

while the queue is not empty:
    take the node with the lowest cost
    ignore it if a cheaper entry was already found
    stop if it is the destination

    for each outgoing edge:
        candidate = current cost + edge cost
        if candidate is cheaper:
            save the new cost
            remember the edge used
            add the neighbour to the queue

The idea is simple. Most of the engineering work lives around that loop.

What I Built

The public function in roadrunner-core accepts five things:

• the directed Graph;
• a source NodeId;
• a destination NodeId;
• a CostModel; and
• a RoutingContext.

It returns a typed RouteResult containing:

• the ordered node path;
• the ordered edge path;
• total physical distance;
• total cost under the selected model;
• the algorithm name; and
• the number of nodes visited during the search.

That last field matters. A route result should explain not only where the router went, but also how much work the algorithm performed to find it.

Problem 1: Rust's Binary Heap Points the Wrong Way

Rust's BinaryHeap is a max-heap: it returns the largest item first. Dijkstra needs the smallest cost first.

I solved this by reversing the comparison for queue entries. A lower route cost is treated as having higher priority. I used f64::total_cmp so floating-point costs have a total ordering, then used NodeId as a stable tie-breaker.

There is another detail: Rust's standard heap does not have a decrease-key operation. When I find a better cost for a node, I push a new entry instead of trying to edit the old one. When an older, more expensive entry eventually leaves the heap, the router compares it with the best known cost and skips it.

This keeps the priority queue implementation small without weakening correctness.

Lesson: A priority queue is not enough by itself. You also need a source of truth for the best known cost and a rule for rejecting stale work.

Problem 2: "Shortest" Does Not Always Mean Distance

The graph stores both distance and base travel time, but Dijkstra does not choose between them. It asks a CostModel to evaluate each edge.

With DistanceCost, a short road is cheap. With TravelTimeCost, a longer but faster road can win. One test builds two routes where the distance model selects A → B → D, while the travel-time model selects A → C → D.

The important part is that the Dijkstra loop does not change.

RouteCost also carries its semantic kind. Distance and travel-time values cannot be silently mixed, and every addition is checked for invalid or overflowing values. If a cost model says it returns distance but produces travel time, routing returns a typed error.

Lesson: Keep graph topology separate from route cost. Traffic-aware and time-dependent costs can evolve without rewriting the shortest-path algorithm.

Problem 3: Finding a Cost Is Not the Same as Returning a Route

During the search, I do not copy a full path into every queue entry. That would create unnecessary allocations as the graph grows.

Instead, every time a cheaper route reaches a node, the router stores one predecessor EdgeId:

destination -> incoming edge -> previous node -> incoming edge -> source

After reaching the destination, route reconstruction walks that chain backwards, collects the edges and nodes, then reverses both lists.

The reconstruction step is defensive. It verifies that each edge exists, that it actually leads to the expected node, and that the predecessor chain cannot exceed the graph's node count. Physical distance is accumulated separately from the selected route cost, so a time-optimized route still reports how far it travels.

Lesson: The algorithm's internal state should be compact, but its output should still be complete and verifiable.

Correctness Included the Awkward Cases

The Phase 5 router had nine focused Dijkstra tests. They covered:

• a graph with a known cheapest path;
• source equal to destination;
• disconnected graphs and unreachable destinations;
• missing source or destination nodes;
• zero-cost cycles;
• distance versus travel-time routing;
• parallel edges between the same nodes;
• equal-cost paths inserted in different orders; and
• a cost model returning the wrong cost kind.

Deterministic ties deserved a dedicated test. Outgoing edges are sorted by destination and edge identity before relaxation, while queue ties use stable node identities. The same graph therefore returns the same selected path even if its edges were inserted in a different order.

Measuring the Baseline

I added a Criterion benchmark rather than describing the implementation as "fast."

The benchmark generates a deterministic directed ring-lattice graph. Every node has three outgoing edges with costs of one, two, and three. Searches begin at node 0 and target the final node, forcing Dijkstra to finalize the complete graph. Graph construction happens outside the timed section.

The initial result was collected on an Apple M3 MacBook Pro with 16 GB RAM using 20 samples per case:

These numbers are a baseline on one synthetic dataset and one machine. They are not a production-scale claim. Memory was deliberately recorded as unavailable because I did not yet have a controlled allocator or profiler configuration.

That honesty is useful: the next routing algorithm now has a result it can compare against under the same conditions.

Tradeoffs I Chose Deliberately

I used HashMap storage for best costs and predecessors because Roadrunner's node IDs are not yet guaranteed to be compact indexes. Indexed vectors could reduce lookup and allocation overhead later, but only after the graph representation provides that guarantee.

I also sort outgoing edges during routing to make ties deterministic. That adds work. For this phase, repeatable behavior was more important than removing an operation I had not yet profiled.

The implementation is roughly O((V + E) log V) with the binary heap. More importantly, it is small enough to inspect and has tests around the parts most likely to fail.

Correct first. Then measure. Then optimize.

The Result

By the end of Phase 5, Roadrunner could calculate a deterministic lowest-cost route across a directed graph, switch between distance and travel-time objectives, reconstruct the complete path, explain how many nodes it visited, and report typed failures instead of ambiguous empty results.

It is still a baseline. It does not use geography to guide the search, so it may explore many nodes that point away from the destination. That is exactly why it is valuable: future A* work can be checked against Dijkstra for identical optimal cost and compared on visited nodes and runtime.

Takeaways

1. The shortest-path loop is the easy part. Queue semantics, stale entries, route reconstruction, and failure handling make it reliable.
2. Cost belongs behind an interface. One algorithm can optimize distance today and travel time tomorrow.
3. Determinism is part of correctness. Stable tie-breaking makes tests, debugging, and benchmarks reproducible.
4. Return evidence with the answer. Path edges, total distance, selected cost, algorithm, and visited-node count make the result explainable.
5. A baseline needs measurements. Even imperfect synthetic benchmarks are more useful than unsupported performance language.