# Dijkstra's single source shortest path algorithm (with Fibonacci heap)

I implemented a generic Dijkstra algorithm. It's lazy since the vertices with their final distances are request on demand. I used the Fibonacci Heap from this question with a few changes (added a copy and move constructor and the copy and swap idiom among other things).

I'm looking for a general review.

Dijkstra's algorithm:

#ifndef DIJKSTRA_ALGORITHM_DIJKSTRA_ALGORITHM_H
#define DIJKSTRA_ALGORITHM_DIJKSTRA_ALGORITHM_H

#include "Graph.h"
#include <limits>
#include "index_fib_heap.h"
#include <type_traits>
#include <functional>
#include <deque>
#include <climits>

namespace mds {

struct identity {
template<typename U>
constexpr auto operator()(U&& v) const noexcept
-> decltype(std::forward<U>(v)) {
return std::forward<U>(v);
}
};

template<typename W,
typename F = identity,
typename IPQ = mds::index_fib_heap<
typename std::remove_reference<
decltype(F()(std::declval<W>()))
>::type
>
>
class dijkstra_algorithm {

using Weight = typename std::remove_reference<
decltype(F()(std::declval<W>()))
>::type;

F               map_w;
IPQ             pq;
const graph<W>  *g;
const edge<W>   **edge_to;
Weight          *distances;

std::pair<std::size_t, Weight> next() {
if (pq.empty()) {
return { SIZE_MAX, { } };
}
auto min = pq.top();
pq.pop();
for (const auto &e : g->adj(min.first)) {
relax(&e);
}
return min;
}

void relax(const edge<W>* edge) {
auto to    = edge->to();
auto new_d = distances[edge->from()]
+ map_w(edge->weight());

if (new_d < distances[to]) {
distances[to] = new_d;
edge_to[to]   = edge;
if (!pq.insert(to, new_d)) {
pq.decrease(to, new_d);
}
}
}

void check(std::size_t v) const {
if (g == nullptr || v >= g->V()) {
throw std::out_of_range("vertex out of range");
}
}

public:

dijkstra_algorithm(std::size_t source, const graph<W>* pg, F pmap_w, IPQ ppq)
: g(pg),
map_w(pmap_w),
edge_to(new const edge<W>*[pg->V()]()),
distances(new Weight[pg->V()]),
pq(std::move(ppq))
{
for (std::size_t i = 0; i < pg->V(); ++i) {
distances[i] = std::numeric_limits<Weight>::max();
}
pq.insert(source, distances[source] = { });
}

dijkstra_algorithm(std::size_t source, const graph<W>* pg, F pmap_w)
: dijkstra_algorithm(source, pg, pmap_w, { pg->V() }) { }

dijkstra_algorithm(std::size_t source, const graph<W>* pg)
: dijkstra_algorithm(source, pg, { }) { }

dijkstra_algorithm(dijkstra_algorithm<W, F, IPQ> && dijkstra) noexcept
: map_w(std::move(dijkstra.map_w)),
pq(std::move(dijkstra.pq)),
g(dijkstra.g),
edge_to(dijkstra.edge_to),
distances(dijkstra.distances)
{
dijkstra.g         = nullptr;
dijkstra.edge_to   = nullptr;
dijkstra.distances = nullptr;
}

dijkstra_algorithm(const dijkstra_algorithm<W, F, IPQ>& dijkstra)
: map_w(dijkstra.map_w),
pq(dijkstra.pq),
g(dijkstra.g)
{
edge_to   = new const edge<W>*[g->V()];
distances = new Weight[g->V()];
for (std::size_t i = 0; i < g->V(); ++i) {
edge_to[i]   = dijkstra.edge_to[i];
distances[i] = dijkstra.distances[i];
}
}

~dijkstra_algorithm() {
delete[] edge_to;
delete[] distances;
}

Weight distance_to(std::size_t v) const {
check(v);
return distances[v];
}

bool has_path(std::size_t v) const {
return distance_to(v) < std::numeric_limits<Weight>::max();
}

std::deque<const edge<W>*> path(std::size_t v) const {
check(v);

std::deque<const edge<W>*> path;
auto e = edge_to[v];
while (e != nullptr) {
path.push_front(e);
e = edge_to[e->from()];
}
return path;
}

friend void swap(dijkstra_algorithm<W, F, IPQ>& first,
dijkstra_algorithm<W, F, IPQ>& second) noexcept {
using std::swap;
swap(first.map_w, second.map_w);
swap(first.pq, second.pq);
swap(first.g, second.g);
swap(first.edge_to, second.edge_to);
swap(first.distances, second.distances);

}

dijkstra_algorithm<W, F, IPQ>& operator=(dijkstra_algorithm<W, F, IPQ> other)  noexcept {
swap(*this, other);
return *this;
}

class dijkstra_iterator
: public std::iterator<std::forward_iterator_tag,
std::remove_cv_t<std::size_t>,
std::ptrdiff_t,
std::size_t*,
std::size_t& >
{

dijkstra_algorithm<W, F, IPQ>*  dijkstra;
std::pair<std::size_t, Weight> current;

public:

explicit dijkstra_iterator(dijkstra_algorithm<W, F, IPQ>*  pdijkstra)
: dijkstra(pdijkstra) {
current = pdijkstra->next();

}

explicit dijkstra_iterator(std::size_t pcurrent)
: current({ pcurrent, { } }) { }

dijkstra_iterator& operator++ () {
current = dijkstra->next();
return *this;
}
dijkstra_iterator operator++ (int) {
dijkstra_iterator tmp(*this);
current = dijkstra->next();
return tmp;
}

bool operator == (const dijkstra_iterator& rhs) const {
return current.first == rhs.current.first;
}

bool operator != (const dijkstra_iterator& rhs) const {
return current.first != rhs.current.first;
}

const std::pair<std::size_t, Weight>& operator* () const {
return current;
}

const std::pair<std::size_t, Weight>&  operator-> () const {
return current;
}
};

using iterator = dijkstra_iterator;
iterator begin() {
return iterator(this);
}

iterator end()  {
return iterator(SIZE_MAX);
}
};
}

#endif //DIJKSTRA_ALGORITHM_DIJKSTRA_ALGORITHM_H


Fibonacci Heap:

#ifndef INDEX_FIB_HEAP_FIB_HEAP_H
#define INDEX_FIB_HEAP_FIB_HEAP_H

#include <algorithm>
#include <stdexcept>
#include <functional>

namespace mds {

template<typename P, typename  Func = std::less<P>>
class index_fib_heap {

struct node {

unsigned index;
P prty;

unsigned degree = 0;
bool mark       = false;
node* parent    = nullptr;
node* childs    = nullptr;
node* left      = nullptr;
node* right     = nullptr;

node(node* n) :
prty(n->prty),
index(n->index),
degree(n->degree),
mark(n->mark) {

}

node(unsigned pindex, const P& priority)
: index(pindex),
prty(priority) { }

node(unsigned pindex, P&& priority)
: index(pindex),
prty(std::move(priority)) { }

n->parent   = parent;
n->left     = this;
n->right    = right;
right->left = n;
right       = n;
return this;
}
node* remove_self() {
left->right = right;
right->left = left;
return this;
}

if (childs == nullptr) {
childs    = n->to_single_list();
n->parent = this;
}
else {
}
n->mark = false;
++degree;
return this;
}

node* to_single_list() {
left  = this;
right = this;
return this;
}
void destroy() {
auto n = childs;
for (auto i = 0u; i < degree; ++i) {
auto next = n->right;
n->destroy();
n = next;
}
delete this;
}

};

node* copy_node(node* n) {
auto new_n = new node(n);
index_table[n->index] = new_n;
return new_n;
}

node* deep_copy(node* root) {
auto copy = copy_node(root);
if (root->childs == nullptr) {
return copy;
}

auto n = root->childs->right;
auto child_copy = deep_copy(root->childs)
->to_single_list();

copy->childs = child_copy;
child_copy->parent = copy;
for (auto i = 1u; i < root->degree; ++i) {
n = n->right;
}
return copy;
}

void consolidate() {
unsigned bound = static_cast<unsigned>(
std::log(N) / LOG_OF_GOLDEN) + 1;
auto degree_array = new node*[bound]();

for (auto n = min; root_size > 0; --root_size) {
auto parent = n;
auto d = parent->degree;
n = n->right;

while (degree_array[d] != nullptr) {
auto child = degree_array[d];
if (cmp(child->prty, parent->prty)) {
std::swap(child, parent);
}
degree_array[d++] = nullptr;
}
degree_array[d] = parent;
}

auto d = 0u;
while (degree_array[d++] == nullptr);

min = degree_array[d - 1]->to_single_list();
for (; d < bound; ++d) {
if (degree_array[d] != nullptr) {
}
}
delete[] degree_array;
++root_size;
}

node* remove_min() {
if (empty()) {
throw std::underflow_error("underflow");
}

auto deleted = min;
deleted->remove_self();
--root_size;

if (deleted == deleted->right) {
min = nullptr;
}
else {
min = min->right;
consolidate();
}
--N;
return deleted;
}

if (cmp(n->prty, min->prty)) {
min = n;
}
++root_size;
}

auto c = n->childs;
auto d = n->degree;
for (auto i = 0u; i < d; ++i) {
auto next = c->right;
c = next;
}
}

template<typename PP>
void decrease_priority(node *n, PP&& new_p) {
if (cmp(n->prty, new_p)) {
throw std::runtime_error("key is greater");
}

n->prty = std::forward<PP>(new_p);
auto p = n->parent;

if (p != nullptr
&& cmp(n->prty, p->prty)) {
cut(n, p);
}
if (cmp(n->prty, min->prty)) {
min = n;
}
}
void cut(node* child, node* parent) {
child->mark = false;
--parent->degree;
if (parent->degree == 0) {
parent->childs = nullptr;
}
else if (parent->childs == child) {
parent->childs = child->right;
}
++root_size;
}

while (n->parent != nullptr && n->mark) {
cut(n, n->parent);
n = n->parent;
}
n->mark = n->mark || n->parent;
}

void check_index(unsigned index) const {
if (index >= max_size) {
std::out_of_range("index out of range");
}
}

static constexpr  double LOG_OF_GOLDEN = 0.4812118;

unsigned max_size;
node**   index_table;
node*    min;
unsigned N;
unsigned root_size;
Func     cmp;

public:

index_fib_heap(unsigned pmax_size, Func pcmp)
: max_size(pmax_size),
index_table(new node*[pmax_size]()),
min(nullptr),
N(0),
root_size(0),
cmp(pcmp) { }

index_fib_heap(unsigned pmax_size)
: index_fib_heap(pmax_size, Func()) { }

index_fib_heap(index_fib_heap<P, Func> && fib) noexcept :
min(fib.min),
N(fib.N),
root_size(fib.root_size),
cmp(fib.cmp),
index_table(fib.index_table),
max_size(fib.max_size)
{
fib.N = fib.max_size = fib.root_size = 0;
fib.index_table = nullptr;
fib.min = nullptr;
}

index_fib_heap(const index_fib_heap<P, Func> & fib) noexcept
: N(fib.N),
root_size(fib.root_size),
cmp(fib.cmp),
max_size(fib.max_size),
index_table(new node*[fib.max_size]())
{
if (fib.empty()) {
return;
}
min    = deep_copy(fib.min)->to_single_list();
auto n = fib.min->right;
for (auto i = 1u; i < root_size; ++i) {
n = n->right;
}
}

~index_fib_heap() {
auto n = min;
for (auto i = 0u; i < root_size; ++i) {
auto next = n->right;
n->destroy();
n = next;
}
delete[] index_table;
}

void pop() {
auto min_node = remove_min();
index_table[min_node->index] = nullptr;
delete min_node;
}

std::pair<unsigned, P> top() const {
return { min->index, min->prty };
}

template<typename PP>
bool insert(unsigned index, PP&& prty) {
check_index(index);
auto &new_node = index_table[index];
if (new_node != nullptr) {
return false;
}
new_node = new node(index,
std::forward<PP>(prty));
if (min == nullptr) {
min = new_node->to_single_list();
++root_size;
}
else {
}
++N;
return true;
}

template<typename PP>
void decrease(unsigned index, PP&& prty) {
check_index(index);
auto node = index_table[index];
if (node != nullptr) {
decrease_priority(node,
std::forward<PP>(prty));
}
}

bool empty() const {
return min == nullptr;
}

unsigned size() const {
return N;
}

bool contains(unsigned index) const {
return index_table[index] != nullptr;
}

friend void swap(index_fib_heap<P, Func>& first, index_fib_heap<P, Func>& second) noexcept {
using std::swap;
swap(first.N, second.N);
swap(first.max_size, second.max_size);
swap(first.index_table, second.index_table);
swap(first.min, second.min);
swap(first.root_size, second.root_size);
swap(first.cmp, second.cmp);
}

index_fib_heap<P, Func>& operator=(index_fib_heap<P, Func> other)  noexcept {
swap(*this, other);
return *this;
}

};
}
#endif //INDEX_FIB_HEAP_FIB_HEAP_H


Graph:

#ifndef GRAPH_GRAPH_H
#define GRAPH_GRAPH_H
#include <cstddef>
#include <vector>

namespace mds {

template <typename W, typename V = std::size_t>
class edge {
V v;
V w;
W wght;

public:
edge(const V& pfrom, const V& pto, const W& pweight)
: v(pfrom), w(pto), wght(pweight) { }

edge(V&& pfrom, V&& pto, W&& pweight)
: v(std::move(pfrom)),
w(std::move(pto)),
wght(std::move(pweight)) { }

V from() const { return v; }
V to() const { return w; }
const W& weight() const { return wght; }
};

template<typename W>
class graph {

public:

graph(std::size_t V)

graph(std::size_t V, std::initializer_list<edge<W>> list)
: graph(V)
{
for (const auto &e : list) {
}
}

check(e.from());
check(e.to());
++edges;
}

}

std::size_t E() const {
return edges;
}

std::size_t V() const {
}

private:
std::size_t edges;

void check(std::size_t v) const {
if (v >= V()) {
throw std::out_of_range("vertex out of range");
}
}
};

}
#endif // GRAPH_GRAPH_H


Client example:

int main() {

mds::graph<std::pair<int, int>> g(9,
{
{ 0, 1, { 4,  3  } },
{ 0, 7, { 8,  7  } },
{ 1, 2, { 8,  7  } },
{ 1, 7, { 11, 10 } },
{ 2, 3, { 7,  6  } },
{ 2, 8, { 2 , 1  } },
{ 2, 5, { 4,  3  } },
{ 3, 4, { 9,  8  } },
{ 3, 5, { 14, 13 } },
{ 4, 5, { 10, 9  } },
{ 5, 6, { 2,  1  } },
{ 6, 7, { 1,  0  } },
{ 6, 8, { 6,  5  } },
{ 7, 8, { 7,  6  } },
{ 1, 0, { 4,  3  } },
{ 7, 0, { 8,  7  } },
{ 2, 1, { 8,  7  } },
{ 7, 1, { 11, 10 } },
{ 3, 2, { 7,  6  } },
{ 8, 2, { 2 , 1  } },
{ 5, 2, { 4,  3  } },
{ 4, 3, { 9,  8  } },
{ 5, 3, { 14, 13 } },
{ 5, 4, { 10, 9  } },
{ 6, 5, { 2,  1  } },
{ 7, 6, { 1,  0  } },
{ 8, 6, { 6,  5  } },
{ 8, 7, { 7,  6  } },
});

using SSSP = mds::dijkstra_algorithm<std::pair<int, int>,
std::function<int(const std::pair<int, int>&)>>;

SSSP da = { 0u, &g, [](const auto& p) { return p.first; } };

for (auto v : da) {
std::cout
<< v.first << " : "
<< v.second << "\n";
}
std::cout << "\n";

for (auto &e : da.path(4)) {
std::cout
<<"From: "  << e->from()
<< " To: "  << e->to()
<< "\n";

std::cout
<<"W1 "   << e->weight().first
<< " W2 " << e->weight().second
<< "\n";
}
}

• Please remember to tag these questions with c++ as well. – Jamal Aug 14 '16 at 0:02