Community realm. Read the code first. Community realm, deployed by its author. Read the code before you interact or send coins.
Package dijkstra finds the cheapest route from one node to every other node of a weighted directed graph, as a pure, ...
gno.land/p/moul/x/daily/dijkstra/v0Cheapest route from one node to every other node of a weighted graph: AddEdge, From, Dist, Path, Order.
1import "gno.land/p/moul/x/daily/dijkstra/v0"
2
3g := dijkstra.New()
4g.AddEdge("depot", "north", 2)
5g.AddEdge("depot", "east", 4)
6g.AddEdge("north", "east", 1)
7
8r := g.From("depot")
9r.Dist("east") // → 3, true (via north, not the direct arc of 4)
10r.Path("east") // → ["depot", "north", "east"]
11r.Order() // → ["depot", "north", "east"], the settle sequence
12r.Dist("somewhere-else") // → -1, false
A realm that routes anything (a fee across hops, a swap across pools, a delivery across a small map) needs the cheapest total, not the fewest steps. A breadth-first walk answers the second question and looks like it answered the first. This answers the first, in O((V+E) log V).
The ordering is total, deliberately. Distance first, then the index the node was added at. Two nodes at the same distance therefore settle in the order the caller built the graph in, identically on every machine that runs it. A search that broke the tie by map iteration order would make a Render built on it differ between validating nodes, which is a consensus bug and not a cosmetic one. An equal-cost relaxation also never displaces the incumbent predecessor, so Path returns the first cheapest route found rather than the last one tried.
Three behaviours worth knowing before you use it:
AddEdge, not at From. It is the algorithm's precondition. A settled node is never revisited, so an accepted negative arc would not produce an error later, it would produce a confident wrong answer, and the caller would have no way to tell.MaxNodes bounds the memory on its own: a node is in the heap at most once, and an improvement moves it rather than duplicating it. Arcs bound the work, not the size.Dist returns (Unreachable, false) for both an unreached node and an unknown name. They are different mistakes with the same remedy, so call Has first when you need to tell them apart. Path returns nil in both cases, never a zero-length path that reads like success.MaxNodes is 512 and MaxEdges is 4000, both 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. Exceeding either panics at build time, where the caller can still do something about it.
A Result is a snapshot. Mutating the graph afterwards does not update it, which is what makes it safe to compute once and hold across a Render.
Live demo: r/moul/x/daily/dijkstrademo.
Part of moul/gno-contracts — moul's versioned gno.land contracts. See the repository for the full catalog, build/test tooling, and usage.
🧪 Highly experimental — potentially vibe-coded. Not audited; may break, change, or be removed at any time. Do not use with anything of value. Full disclaimer: DISCLAIMER.
Package dijkstra finds the cheapest route from one node to every other node of a weighted directed graph, as a pure, reusable package.
It is Dijkstra's algorithm with a binary min-heap keyed on node index, so a node is never queued twice and the queue never grows past the node count. Complexity is O((V+E) log V), and both V and E are capped (MaxNodes, MaxEdges) so a realm can reason about the gas before it calls.
The result is *deterministic*. Two nodes sitting at the same distance settle in the order they were added to the graph, and a relaxation that merely ties the incumbent never replaces it, so the predecessor chain Path walks is the same on every node that runs the code. A shortest-path routine that broke ties by map iteration order would make a Render differ between validators, which is a consensus bug rather than a cosmetic one.
Weights are non-negative by construction: AddEdge panics on a negative one. That is not a simplification, it is the precondition the algorithm needs. A settled node is never revisited, so one negative edge silently returns a wrong answer rather than an error.
A live demo of this package is at r/moul/x/daily/dijkstrademo(/r/moul/x/daily/dijkstrademo/v0).
1const (
2 // MaxNodes bounds the graph so a caller can size gas up front.
3 MaxNodes = 512
4 // MaxEdges bounds the arcs for the same reason. Both are deliberately
5 // small: this is a package for a realm's routing table, not for a road
6 // network.
7 MaxEdges = 4000
8 // Unreachable is the distance reported for a node no path reaches. It is
9 // returned alongside ok=false, never on its own.
10 Unreachable = -1
11)ErrUnknownNode is returned by lookups naming a node the graph never saw.
Graph is a weighted directed graph over named nodes. The zero value is not usable, build one with New.
AddEdge records a one-way arc from -> to costing weight, registering either endpoint that is new. Parallel arcs are kept rather than collapsed: the search takes the cheapest, and dropping the others would lose information a caller may want to render.
It panics on a negative weight (the algorithm's precondition), on a self-loop (it can never shorten a path and is always a caller mistake), and past MaxEdges.
AddNode registers a node with no arcs and returns its index. Adding a node twice returns the existing index and changes nothing, which is how a caller declares an island that nothing reaches.
It panics on an empty name, and past MaxNodes.
AddUndirected records the same cost in both directions. It is two arcs and counts as two against MaxEdges, because that is what it is.
Edges returns the number of arcs. An AddUndirected call contributes two.
From runs the search outward from source and returns the distances to every node. It panics when source is not in the graph, because a typo'd source silently returning "nothing is reachable" is the failure mode this package exists to avoid.
Has reports whether the graph knows a node by that name.
Len returns the number of nodes.
Names returns the node names in insertion order. The slice is a copy, so a caller cannot reorder the graph's own index by sorting it.
Result holds one single-source run. It is a snapshot: mutating the graph afterwards does not update it.
Dist returns the total weight of the cheapest route to name. ok is false for a node no route reaches and for a name the graph does not know, which are different mistakes with the same remedy: check Has first if you need to tell them apart.
Order returns the nodes in the sequence the search settled them: the source first, then always the closest node still outstanding. That sequence is the algorithm, and a demo that shows it teaches more than one that prints only the answer.
Path returns the cheapest route to name, source first and name last. It returns nil when no route reaches name, and a one-element slice for the source itself.
PathString renders Path joined with sep, or "" when there is no route. It exists so a Render does not have to carry its own join loop.
Reachable returns how many nodes have a route, the source included.
Relaxations returns how many arcs the run actually improved a distance with. It is the honest cost figure: the arc count is what was looked at, this is what was paid for.
Source returns the node the run started from.
Via returns the node immediately before name on the cheapest route, and false for the source and for anything unreachable.
