Dijkstra
Dijkstra's shortest-path and priority-ordered traversal algorithms.
Dijkstra's algorithm finds the shortest (lowest total weight) path from a source vertex to one or all reachable vertices in a graph with non-negative edge weights. It uses a min-heap priority queue to always expand the cheapest known vertex next.
Non-negative weights only
Dijkstra's algorithm produces incorrect results if any edge weight is negative. Use BellmanFord when negative weights are possible.
Priority traversal
Dijkstra.toIterator and Dijkstra.toArray let
you traverse all reachable vertices in ascending accumulated-cost
order — useful for budget-limited flood fill, range queries, and
influence-map generation:
for vertex, costFromStart in Dijkstra.toIterator(origin, getNeighbors, getWeight) do
if costFromStart > budget then break end
markInRange(vertex)
end
All functions accept either callback form for GetNeighbors — see
GraphUtil for details.
Example graph
-- 2 1
-- A ───── B ───── D
-- │ │
-- 3 5
-- │ │
-- C ───────────────┘
local weights = {
A = { B = 2, C = 3 },
B = { A = 2, D = 1 },
C = { A = 3, D = 5 },
D = { B = 1, C = 5 },
}
local function getNeighbors(v) return weights[v] and (function()
local keys = {}
for k in pairs(weights[v]) do table.insert(keys, k) end
return keys
end)() or {} end
local function getWeight(from, to) return weights[from][to] end
Functions
shortestPath
directedundirected
Finds the shortest weighted path from start to goal and returns a
PathResult, or nil if goal is unreachable.
local result = Dijkstra.shortestPath("A", "D", getNeighbors, getWeight)
-- result.path == { "A", "B", "D" }
-- result.cost == 3 (2 + 1)
Pass an optional ShouldStop predicate to abort a
long-running search — checked once per expanded vertex (after the goal check),
returning true stops the search and returns nil:
-- Stop once the cheapest frontier vertex exceeds a budget of 500.
local result = Dijkstra.shortestPath(start, goal, getNeighbors, getWeight, function(_vertex, cost)
return cost > 500
end)
Time complexity: O((V + E) log V) with a binary min-heap.
bidirectionalShortestPath
directedundirected
Finds the shortest weighted path between start and goal by
running Dijkstra from both ends simultaneously — alternately expanding
whichever heap has the cheaper next vertex — and stopping as soon as the
two searches are provably guaranteed to have met at the shortest
possible point. Returns the same PathResult
as Dijkstra.shortestPath, or nil if goal is
unreachable.
local result = Dijkstra.bidirectionalShortestPath("A", "D", getNeighbors, getWeight)
-- result.path == { "A", "B", "D" }
-- result.cost == 3
:::caution Directed graphs
Growing a search backward from goal requires walking edges in
reverse. By default this function reuses getNeighbors for both
directions, which is only correct for undirected graphs. For a
directed graph, pass a callback that returns the predecessors of a
vertex (i.e. getReversedNeighbors(v) returns every u such that
u → v is an edge) — the edge weight is still looked up as
getWeight(u, v), so no separate reverse-weight callback is needed:
-- Directed graph where reverseAdj[v] lists v's predecessors
local function getReversedNeighbors(v)
return reverseAdj[v]
end
local result = Dijkstra.bidirectionalShortestPath(
"A", "D", getNeighbors, getWeight, getReversedNeighbors
)
:::
An optional ShouldStop predicate (passed after
getReversedNeighbors) aborts the search and returns nil — it is checked
each time either side settles a vertex.
Time complexity: O((V + E) log V), but typically explores far fewer
vertices in practice since each side only has to reach roughly halfway.
distances
directedundirectedDijkstra.distances() → {[V]: number}
Runs Dijkstra from start to completion and returns a map of every
reachable vertex to its shortest distance from start. Unreachable
vertices are absent from the table.
local d = Dijkstra.distances("A", getNeighbors, getWeight)
print(d["B"]) -- 2
print(d["C"]) -- 3
print(d["D"]) -- 3
Pass an optional ShouldStop predicate to abort a long-running flood — checked once per settled vertex. Unlike the path-finders, on early stop this returns the partial distance map accumulated so far (every vertex settled before the stop is present and final):
-- Only compute distances out to a budget of 10.
local d = Dijkstra.distances(start, getNeighbors, getWeight, function(_vertex, cost)
return cost > 10
end)
Time complexity: O((V + E) log V) with a binary min-heap.
toIterator
directedundirected
Returns a lazy iterator that yields (vertex, costFromStart) pairs in
ascending accumulated-cost order — every vertex is visited before any
vertex that is reachable through it at higher cost.
The iterator drives the heap expansion internally via a closure; no
coroutines are used. You can break early to stop expansion, which is
the key advantage over Dijkstra.distances.
Aliased as Dijkstra.forEach.
-- Visit all nodes within a travel budget of 5
for vertex, cost in Dijkstra.toIterator(origin, getNeighbors, getWeight) do
if cost > 5 then break end
table.insert(inRange, vertex)
end
for-loop usage
for vertex, cost in Dijkstra.toIterator(start, getNeighbors, getWeight) do
print(vertex, cost)
end
Time complexity per call: amortised O(degree(V) · log V)
forEach
directedundirectedAlias of Dijkstra.toIterator.
toArray
directedundirected
Runs Dijkstra from start to completion and returns an array of
VisitRecord values in ascending accumulated-cost
order.
local records = Dijkstra.toArray("A", getNeighbors, getWeight)
for _, record in records do
print(record.vertex, record.cost)
end
-- A 0
-- B 2
-- C 3
-- D 3
Time complexity: O((V + E) log V) with a binary min-heap.