Here is an implementation of Dijkstra
As an rags-to-riches
version of this Object oriented approach to Dijkstra's algorithm
#include <set>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
#include <iterator>
#include <iostream>
/*
A very simple Graph object:
The graph type here is only supposed to provide a very simplistic implementation of a graph. The point is that it provides the minimum requirements that are needed by Dijkstra algorithm.
*/
namespace ThorsAnvil
{
template<typename N, typename IdType = N>
class Graph
{
class Node;
using NodeHolder = typename std::set<Node>;
public:
using NodeId = IdType;
using NodeRef = typename NodeHolder::iterator;
using Edges = std::vector<std::pair<NodeRef, int>>;
private:
class Node
{
N data;
mutable Edges outedge;
public:
Node(N const& data)
: data(data)
{}
void addEdge(NodeRef e, int cost) const
{
outedge.emplace_back(e, cost);
}
NodeId const& id() const
{
return data;
}
Edges const& getEdges() const
{
return outedge;
}
friend bool operator<(Node const& lhs, Node const& rhs)
{
return lhs.data < rhs.data;
}
};
NodeHolder nodes;
public:
NodeRef addNode(N const& data)
{
auto result = nodes.emplace(data);
return result.first;
}
NodeRef getRef(N const& data)
{
return nodes.find(data);
}
void addEdge(NodeRef src, NodeRef dst, int cost)
{
if (src != nodes.end() && dst != nodes.end()) {
src->addEdge(dst, cost);
}
}
Edges const& getEdges(N const& node) const
{
static Edges const empty;
NodeRef nodeInfo = nodes.find(node);
if (nodeInfo == nodes.end()) {
return empty;
}
return nodeInfo->getEdges();
}
};
/*
Dijkstra class
*/
template<typename Graph>
class Dijkstra
{
// Graph: The graph type we will traverse
// Graph::NodeRef Type that defines references to the nodes.
// Graph::NodeId A type that uniquely identifies a node.
// nodeRef->id() Gives a unique ID that identifies the node.
// So we don't need to processes it more than once.
// nodeRef->getEdges() returns a container with {NodeRef, Cost}
using NodeRef = typename Graph::NodeRef;
using NodeId = typename Graph::NodeId;
/*
QueInfo
*/
// Its a tuple really:
// It is used in a priority queue used by the route algorithm
// 1: The node we have reached.
// 2: The cost to get to this node.
// 3: An ordered list of nodes to get here with this cost.
struct QueInfo: public std::tuple<NodeRef, int, std::vector<NodeRef>>
{
public:
QueInfo(QueInfo const&) = default;
QueInfo(NodeRef const& data, int cost, std::vector<NodeRef> const& route)
: std::tuple<NodeRef, int, std::vector<NodeRef>>(data, cost, route)
{
// Add the current node to the end of the route
std::get<2>(*this).push_back(data);
}
// Allow QueInfo to be ordered (for the priority queue
friend bool operator<(QueInfo const& lhs, QueInfo const& rhs)
{
return std::get<1>(lhs) > std::get<1>(rhs);
}
};
/*
Dijkstra (Members and constructor)
*/
Graph const& graph;
public:
Dijkstra(Graph const& graph)
: graph(graph)
{}
/*
Dijkstra algorithm implementation.
*/
std::vector<NodeRef> route(NodeRef const& src, NodeRef const& dst)
{
std::set<NodeId> found;
std::priority_queue<QueInfo> frontier;
frontier.emplace(src, 0, std::vector<NodeRef>());
while(!frontier.empty()) {
QueInfo next = frontier.top();
frontier.pop();
NodeRef const& current = std::get<0>(next);
if (found.find(current->id()) != found.end()) {
continue;
}
found.emplace(current->id());
std::vector<NodeRef> const& result = std::get<2>(next);
if (current == dst) {
return result;
}
for(auto const& loop: current->getEdges()) {
frontier.emplace(loop.first, std::get<1>(next) + loop.second, result);
}
}
return {};
}
};
}
/*
An Example Main:
*/
template<typename T>
struct RefPrinter
{
T const& data;
RefPrinter(T const& data) : data(data) {}
friend std::ostream& operator<<(std::ostream& str, RefPrinter const& value)
{
return str << value.data->id();
}
};
int main()
{
using Graph = ThorsAnvil::Graph<std::string>;
using Dijkstra = ThorsAnvil::Dijkstra<Graph>;
Graph graph;
for(auto const& it : {"a","b","c","d","e","f","g"}) {
graph.addNode(it);
}
for(auto const& it : std::initializer_list<std::pair<std::string, std::string>>{
{"a","b"},{"b","c"},{"c","d"},
{"b","a"},{"c","b"},{"d","c"},
{"c","e"},{"e","f"},{"b","f"},
{"e","c"},{"f","e"},{"f","b"},
{"f","g"},{"a","g"},
{"g","f"},{"g","a"}
}) {
graph.addEdge(graph.getRef(it.first), graph.getRef(it.second), 1);
}
Dijkstra dijkstra(graph);
auto result = dijkstra.route(graph.getRef("a"), graph.getRef("e"));
std::copy(std::begin(result), std::end(result),
std::ostream_iterator<RefPrinter<Graph::NodeRef>>(std::cout, "\n"));
}