Skip to content Search Apps Documentation Source Content File Folder Download Copy Actions State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

Community realm. Read the code first. Community realm, deployed by its author. Read the code before you interact or send coins.

Dijkstra

The cheapest route from one node to every other node of a weighted graph, demoing the p/moul/x/daily/dijkstra library.

The network

Arcs are one-way. 7 nodes, 7 arcs, searched from depot.

from to cost
depot north 2
depot east 4
north east 1
north ridge 3
east port 6
ridge port 3
port beacon 2

quarry is in the graph with no arcs at all.

Cheapest route to each node

node distance arrives via route
depot 0 source depot
north 2 depot depot -> north
east 3 north depot -> north -> east
ridge 5 north depot -> north -> ridge
port 8 ridge depot -> north -> ridge -> port
beacon 10 port depot -> north -> ridge -> port -> beacon
quarry unreachable

Two of those rows are the point of the algorithm. east is reachable directly for 4, and the answer is 3, through north. port is first offered at 9 by east, and ends at 8 through ridge, which the search only discovers two settlements later.

The order the search settles nodes

Always the closest node still outstanding, never the next one along an arc. That is the whole difference from a breadth-first walk, and it is why a cheap long way round still wins.

step settles at distance
1 depot 0
2 north 2
3 east 3
4 ridge 5
5 port 8
6 beacon 10

6 of 7 nodes were reached, in 7 improvements. An arc that is looked at and rejected costs a comparison; only an improvement costs a write.

Ties, and why a realm should care

Three spokes, all 5 away from the hub. Nothing in the distances separates them, so something else has to, and that something must not be map iteration order: a Render that reshuffled between validating nodes would be a consensus bug, not a cosmetic one.

declared settle order
west, south, crater hub -> west -> south -> crater
crater, south, west hub -> crater -> south -> west

The tie resolves to the order the graph was built in, and nothing else. Build it the same way twice and you get the same page twice.

What it will not do

A negative arc panics at AddEdge, where the caller can still fix it. Accepting one would not return an error later, it would return a confident wrong answer: the search never revisits a settled node, so a negative arc pointing back at one is simply never seen.

limit value why
MaxNodes 512 the frontier holds at most one entry per node, so this bounds memory
MaxEdges 4000 arcs bound the work, not the memory
negative arc panics the algorithm's precondition, not a simplification
self-loop panics it can never shorten a path, so it is a caller mistake

Both caps are small on purpose. This is a routing table for a realm, not a road atlas, and a caller that can state the worst case up front can price the gas before it sends the transaction.