Header-only C++ Dijkstra implementation
This repository contains a single C++ header file dijkstra.hpp
providing a slim interface.
I created this for my other repository which can genreate model railroad timesaver puzzles and I wanted it to also provide a best answer ;)
C++14, tested with Visual Studio 2022 (As it needs to run on a microcontroller which compiler does not support the most recent C++ standards, I cannot use the newest features.)
The Dijkstra template takes a _Distance
type and optional _Tidx
type, defaulting to size_t
.
class Step;
using Steps = std::vector<Step>;
using Dijk = Dijkstra<_Distance = unsigned long>;
The constructor takes an infinite
and unset
property, the later defaulting to -1
. Both are used for settingthe internal data structures and need to match the _Distance
and _Tidx
types.
Dijk dijkstra(-1);
The dijkstra
method takes a collection size and the index to the first node to start from. Internally, all mechanisms are handled on a index basis. So remember to keep your collection stable between the dijkstra
call and the shortestPath
calculation!
Additionally, two callback methods need to be provided:
std::function<const std::vector<size_t>(const size_t)> neighbors;
std::function<const _Distance(const size_t, const size_t, PreviousCallback)> distance;
neighbors
provides a list of connected nodes to the algorithm and distance
calculates the length of an edge between two nodes. To better calculate the distance, the whole path can be retrieved via the PreviousCallback
// calculate all paths
Dijk dijkstra;
dijkstra.dijkstra(this->steps.size(), 0,
[&](const size_t i) -> const std::vector<size_t> {
std::vector<size_t> neighbors;
for (auto neighbor : steps[i].actions)
neighbors.push_back(neighbor.target);
return neighbors;
},
[&](const size_t a, const size_t b, PreviousCallback prec) -> const unsigned int {
for (auto neighbor : steps[a].actions)
if (neighbor.target == b)
return (unsigned int)1;
return 0;
}
);
A call to shortestPath
with a index from the Nodes
collection will then calculate the shortes path, returning a vector of indices:
// get shortest path to target
using Path = std::vector<const size_t>;
Path path = dijkstra.shortestPath(&target);
To execute the time consuming dijkstra alogrithm on large graphs also in an event based environment without blocking, two indiviual methods are provided:
// init
dijkstra_init(nodesCount, start);
// dijkstra
while (dijkstra_step(neighbors, distance));
This allows the execution on systems with a watchdog, e.g. a browser. It is equivalent to the dijkstra.dijkstra(nodes, start, neighbors, distance)
call.
Also see example.cpp which is used for the status badge.
Let me know of any comments, remarks or additions.