Dijkstra’s algorithm
#
NOTE: Dijkstra == Astar when heuristicCostEstimate() of Astar return 0!!
Dijkstra’s algorithm to find the shortest path between a and b.
It picks the unvisited vertex with the lowest distance,
calculates the distance through it to each unvisited neighbor,
and updates the neighbor’s distance if smaller.
Mark visited (set to red) when done with neighbors.
| Name | Value |
|---|---|
| Class | Search algorithm |
| Data structure | Graph |
| Worst-case performance |  |
实现
Pseudocode
In the following algorithm, the code u ← vertex in Q with min dist[u],
searches for the vertex u in the vertex set Q that has the least dist[u] value. length(u, v) returns the length of the edge joining (i.e. the distance between) the two neighbor-nodes u and v.
The variable alt on line 18 is the length of the path from the root node to the neighbor node v if it were to go through u.
If this path is shorter than the current shortest path recorded for v,
that current path is replaced with this alt path.
The prev array is populated with a pointer to the “next-hop” node on the
source graph to get the shortest route to the source.
Using a priority queue
A min-priority queue is an abstract data type that provides 3 basic operations:
add_with_priority(), decrease_priority() and extract_min().
As mentioned earlier, using such a data structure can lead to faster computing times than using a basic queue.
Notably, Fibonacci heap (Fredman & Tarjan 1984) or Brodal queue offer optimal implementations for those 3 operations.
As the algorithm is slightly different, we mention it here, in pseudo-code as well:
An implementation with min priority queue
NOTE when implements, data structure is min priority(heap), so min ls back()!
/**
* @file dijkstra.hpp
* @author y.
*/
#pragma once
#include <unordered_map> // unordered_map
#include <limits> // numeric_limits
#include <algorithm> // push_heap ..
namespace yuiwong
{
/**
* @struct DijkstraGraph
* Graph for dijkstra algorithm implementation
*
* @note
* - Dijkstra == Astar when heuristicCostEstimate() of Astar return 0
* - NOT for MT (NOT MT-safe)
*
* @tparam Id vertex ID type, id to identify a unique vertex, default
* int32_t
* @tparam Edge edge distance type, default double, the distance is
* distance of the edge of vertex a and vertex b
*/
template<typename Id = int32_t, typename Edge = double>
struct DijkstraGraph {
using Distance = Edge;///< Distance alias
/**
* Edges type of a vertex: { destVertexId, Distance }
* @note destVertexId should NOT == id of this vertex, else distance
* should be 0
*/
using Edges = std::unordered_map<Id, Distance>;
/// Vertices type of a graph for dijkstra: { VertexId, Edges }
using Vertices = std::unordered_map<Id, Edges>;
/// Dtor
~DijkstraGraph() noexcept;
/**
* Check whether has vertex of id
* @param id vertex id
* @return true if vertex found, else false
*/
inline bool hasVertex(Id const& id) const noexcept;
/**
* Check whether has edge of vertex of id to vertex of destVertexId
* @param id vertex id
* @param destVertexId dest vertex id
* @return true if edge found, else false
*/
bool hasEdge(Id const& id, Id const& destVertexId) const noexcept;
//bool addVertex(Id const& id, Edges&& edges) noexcept;
//bool addVertex(Id const& id, Edges const& edges) noexcept;
/**
* Add dest vertex for this vertex with distance and override check
* @note
* - edge only for vertex -> dest vertex
* - NOT need to add vertex a -> a with distance == 0
* @param id this vertex id
* @param destVertexId dest vertex id
* @param edge the distance of this vertex to dest vertex, i.e.
* the edge of this vertex -> dest vertex
* @return true when add successfully, false when @a destVertexId
* exists or @a distance invalid
* @sa
* - hasEdge
* - updateVertex
*/
virtual bool addVertex(
Id const& id,
Id const& destVertexId,
Edge const& edge) noexcept;
/**
* Add or update dest vertex for this vertex with distance check
* @note
* - edge only for vertex -> dest vertex
* - NOT need to add vertex a -> a with distance == 0
* @param id this vertex id
* @param destVertexId dest vertex id
* @param edge the distance of this vertex to dest vertex, i.e.
* the edge of this vertex -> dest vertex
* @return true when add successfully, false when @a distance invalid
* @sa
* - hasEdge
* - addVertex
*/
virtual bool updateVertex(
Id const& id,
Id const& destVertexId,
Edge const& edge) noexcept;
/**
* Get edge distance of this vertex to dest vertex
* @param id this vertex id
* @param destVertexId dest vertex id
* @return distance when both vertex and edge exists
* @throw std::logic_error when vertex or dest vertex NOT exists
*/
Distance getEdge(Id const& id, Id const& destVertexId) const;
/**
* Get edges of this vertex
* @param id this vertex id
* @return edges of this vertex
* @throw std::logic_error when vertex NOT exists
*/
Edges const& getEdges(Id const& id) const;
/// @return vertices
inline Vertices const& getVertices() const noexcept;
/// @return vertices size
inline uint32_t getSize() const noexcept;
/// Clear vertices
inline void clear() noexcept;
/// Remove vertex by @a id
bool removeVertex(Id const& id) noexcept;
/// Remove edge of vertex of @a id -> vertex of @a destVertexId
bool removeEdge(Id const& id, Id const& destVertexId) noexcept;
protected:
Vertices vertices;///< Graph vertices
};
/**
* @struct Dijkstra
* Dijkstra algorithm implementation
*
* @note NOT for MT (NOT MT-safe)
* @tparam Graph graph type for Dijkstra
* @tparam Id vertex ID type, id to identify a unique vertex, default
* int32_t
* @tparam Edge edge distance type, default double, the distance is
* distance of the edge of vertex a and vertex b
*
* @sa https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
*/
template<typename Id = int32_t, typename Edge = double>
struct Dijkstra {
using Distance = Edge;///< Distance alias
/**
* Compute shortest path from @a start to @a goal
* @note
* - Using a min priority queue
* (NOTE when implements, data structure is min priority queue(heap),
* so min ls back()!)
* - Only when @a start == @a goal, then result has 1 vertex, else
* result > 1 vertex
* @param graph graph to compute shortest path
* @param start start vertex id
* @param goal goal vertex id
* @param[out] distance if NOT nil set to total distance when success
* @return shortest path when success (NOT empty)
* @throw std::logic_error when start or goal invalid or cannot find path
* @sa
* - https://en.wikipedia.org/wiki/Dijkstra's_algorithm#Pseudocode
* - https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Using_a_priority_queue
*/
template<typename Graph>
typename std::enable_if<
std::is_base_of<DijkstraGraph<Id, Edge>, Graph>::value
|| std::is_same<DijkstraGraph<Id, Edge>, typename std::decay<Graph>::type>::value,
std::vector<Id> >::type solve(
Graph const& graph,
Id const& start,
Id const& goal,
Distance* const distance = nullptr) const;
};
/// Int32_t + double dijkstra implements
using DijkstraId = Dijkstra<int32_t, double>;
/// String + double dijkstra implements
using DijkstraSd = Dijkstra<std::string, double>;
template<typename Id, typename Edge>
DijkstraGraph<Id, Edge>::~DijkstraGraph() noexcept {}
template<typename Id, typename Edge>
inline bool DijkstraGraph<Id, Edge>::hasVertex(Id const& id) const noexcept
{
return this->vertices.find(id) != this->vertices.cend();
}
template<typename Id, typename Edge>
bool DijkstraGraph<Id, Edge>::hasEdge(
Id const& id, Id const& destVertexId) const noexcept
{
auto const eit = this->vertices.find(id);
if (eit == this->vertices.cend()) {
return false;
}
auto const& edges = eit->second;
return edges.find(destVertexId) != edges.cend();
}
template<typename Id, typename Edge>
bool DijkstraGraph<Id, Edge>::addVertex(
Id const& id, Id const& destVertexId, Edge const& edge) noexcept
{
// Check 0
if ((id == destVertexId)
&& (std::abs(edge) > std::numeric_limits<Distance>::epsilon())) {
return false;
}
// Check exists
auto const eit = this->vertices.find(id);
if (eit != this->vertices.end()) {
auto const& edges = eit->second;
if (edges.find(destVertexId) != edges.end()) {
return false;
}
}
// Add
this->vertices[id][destVertexId] = edge;
return true;
}
template<typename Id, typename Edge>
bool DijkstraGraph<Id, Edge>::updateVertex(
Id const& id, Id const& destVertexId, Edge const& edge) noexcept
{
// Check 0
if ((id == destVertexId)
&& (std::abs(edge) > std::numeric_limits<Distance>::epsilon())) {
return false;
}
// Add or update
this->vertices[id][destVertexId] = edge;
return true;
}
template<typename Id, typename Edge>
typename DijkstraGraph<Id, Edge>::Distance
DijkstraGraph<Id, Edge>::getEdge(Id const& id, Id const& destVertexId) const
{
auto const eit = this->vertices.find(id);
if (eit == this->vertices.cend()) {
throw std::logic_error("this vertex NOT exists");
}
auto const& edges = eit->second;
auto const edit = edges.find(destVertexId);
if (edit == edges.cend()) {
throw std::logic_error("dest vertex NOT exists");
}
return edit->second;
}
template<typename Id, typename Edge>
typename DijkstraGraph<Id, Edge>::Edges const&
DijkstraGraph<Id, Edge>::getEdges(Id const& id) const
{
auto const eit = this->vertices.find(id);
if (eit == this->vertices.cend()) {
throw std::logic_error("this vertex NOT exists");
}
return eit->second;
}
template<typename Id, typename Edge>
inline typename DijkstraGraph<Id, Edge>::Vertices const&
DijkstraGraph<Id, Edge>::getVertices() const noexcept
{
return this->vertices;
}
template<typename Id, typename Edge>
inline uint32_t DijkstraGraph<Id, Edge>::getSize() const noexcept
{
return this->vertices.size();
}
template<typename Id, typename Edge>
inline void DijkstraGraph<Id, Edge>::clear() noexcept
{
this->vertices.clear();
}
template<typename Id, typename Edge>
inline bool DijkstraGraph<Id, Edge>::removeVertex(Id const& id) noexcept
{
auto it = this->vertices.find(id);
if (it != this->vertices.end()) {
this->vertices.erase(it);
return true;
}
return false;
}
template<typename Id, typename Edge>
inline bool DijkstraGraph<Id, Edge>::removeEdge(
Id const& id, Id const& destVertexId) noexcept
{
auto it = this->vertices.find(id);
if (it != this->vertices.end()) {
auto eit = it->second.find(destVertexId);
if (eit != it->second.end()) {
it->second.erase(eit);
if (it->second.empty()) {
this->vertices.erase(it);
}
return true;
}
}
return false;
}
/// Operator<< for DijkstraGraph
template<typename Id, typename Edge>
std::ostream& operator<<(std::ostream& os, DijkstraGraph<Id, Edge> const& g) noexcept
{
os << '(' << g.getSize() << ") ";
for (auto const& v : g.getVertices()) {
for (auto const& e : v.second) {
os << v.first << "->" << e.first << ':' << e.second << ";";
}
os << "; ";
}
return os;
}
template<typename Id, typename Edge>
template<typename Graph>
typename std::enable_if<
std::is_base_of<DijkstraGraph<Id, Edge>, Graph>::value
|| std::is_same<DijkstraGraph<Id, Edge>, typename std::decay<Graph>::type>::value,
std::vector<Id> >::type Dijkstra<Id, Edge>::solve(
Graph const& graph,
Id const& start,
Id const& goal,
Distance* const distance) const
{
//// Check start and goal
//if (!this->graph.hasVertex(start) || !this->graph.hasVertex(goal)) {
// throw std::logic_error("start or goal invalid");
//}
std::unordered_map<Id, Distance> distances;
auto const comparator = [&distances](Id const& left, Id const& right) {
return distances[left] > distances[right];
};
std::vector<Id> nodes;
auto const maxd = std::numeric_limits<Distance>::max();
// Initialization
for (auto const& vertex : graph.getVertices()) {
if (vertex.first == start) {
// Distance from source to source
distances[start] = Distance(0);
} else {
// Unknown distance from source to v
distances[vertex.first] = maxd;
}
// Add vertex to Q: Q.add_with_priority(v, dist[v])
// All nodes initially in Q (unvisited nodes)
// Max is first, min is last
nodes.push_back(vertex.first);
std::push_heap(nodes.begin(), nodes.end(), comparator);
}
// Previous node in optimal path from source
std::unordered_map<Id, Id> previous;
// The main loop
std::vector<Id> path;
auto const eps = std::numeric_limits<Distance>::epsilon();
while (!nodes.empty()) {
// Node with the least distance will be selected first
// If comparator is less => removes the largest element from a max heap,
// but here comparator is greater => removes smallest
std::pop_heap(nodes.begin(), nodes.end(), comparator);
Id smallest = nodes.back();
nodes.pop_back();
// Check whether done
if (goal == smallest) {
// Fill path from goal to start(NO start)
//auto const end = previous.end();
//while (previous.find(smallest) != end) {
// path.push_back(smallest);
// smallest = previous[smallest];
//}
for (auto it = previous.find(smallest), end = previous.end();
it != end; it = previous.find(smallest)) {
path.push_back(smallest);
smallest = it->second;
}
break;
}
// Check whether start or goal invalid
if (std::abs(maxd - distances[smallest]) <= eps) {
throw std::logic_error("start or goal invalid 2");
//break;
}
// Where neighbor is still in Q
auto const& edges = graph.getEdges(smallest);
//for (auto const& neighbor : graph.vertices[smallest]) {...}
for (auto const& neighbor : edges) {
// alt ← dist[u] + length(u, v)
Distance alt = distances[smallest] + neighbor.second;
// A shorter path to neighbor vertex has been found
auto const& nei = neighbor.first;
if (alt < distances[nei]) {
distances[nei] = alt;
previous[nei] = smallest;
// Q.decrease_priority(v, alt) (alt has updated to distances):
std::make_heap(nodes.begin(), nodes.end(), comparator);
}
}
}
// Check whether unreachable
if (path.empty() && (start != goal)) {
throw std::logic_error("cannot find path");
}
// Add start to back
path.push_back(start);
// Reverse to start->goal
std::reverse(path.begin(), path.end());
// Done successfully
if (distance) {
*distance = distances[goal];
}
return std::move(path);
}
} // namespace yuiwong
Dijkstra test
TEST(Dijkstra, solve)
{
Dijkstra<int32_t, double> dijkstra;
DijkstraGraph<int32_t, double> g;
EXPECT_FALSE(g.hasVertex(0));
EXPECT_FALSE(g.hasVertex(-1));
EXPECT_FALSE(g.hasVertex(100));
EXPECT_FALSE(g.hasVertex(3));
EXPECT_FALSE(g.hasEdge(0, -1));
EXPECT_FALSE(g.hasEdge(0, 100));
EXPECT_FALSE(g.hasEdge(0, 3));
EXPECT_THROW(g.getEdge(0, -1), std::logic_error);
//
EXPECT_TRUE(g.addVertex(0, -1, 3.2));
EXPECT_FALSE(g.addVertex(0, -1, 3.3));
EXPECT_DOUBLE_EQ(g.getEdge(0, -1), 3.2);
EXPECT_TRUE(g.updateVertex(0, -1, 3.3));
EXPECT_DOUBLE_EQ(g.getEdge(0, -1), 3.3);
EXPECT_TRUE(g.addVertex(0, 3, 200));
EXPECT_TRUE(g.addVertex(-1, 3, 20));
EXPECT_TRUE(g.addVertex(100, 3, 10));
EXPECT_TRUE(g.addVertex(3, 100, 11.23));
EXPECT_TRUE(g.addVertex(3, 5, -10));
EXPECT_TRUE(g.addVertex(5, 7, 2));
EXPECT_FALSE(g.addVertex(7, 7, 2e3));
EXPECT_TRUE(g.addVertex(7, 7, 0));
//
double d = -1;
auto path = dijkstra.solve(g, -1, 100, &d);
for (auto const& p : path) {
std::cout << p << '\n';
}
std::cout << "d: " << d << '\n';
EXPECT_THROW(dijkstra.solve(g, 100, -1), std::logic_error);
std::cout << g << '\n';
d = -1;
path = dijkstra.solve(g, -1, 7, &d);
for (auto const& p : path) {
std::cout << p << '\n';
}
std::cout << "d: " << d << '\n';
//
d = -1;
path = dijkstra.solve(g, -1, -1, &d);
for (auto const& p : path) {
std::cout << p << '\n';
}
std::cout << "d: " << d << '\n';
//
d = -1;
path = dijkstra.solve(g, 7, 7, &d);
for (auto const& p : path) {
std::cout << p << '\n';
}
std::cout << "d: " << d << '\n';
//
EXPECT_TRUE(g.hasVertex(0));
EXPECT_TRUE(g.hasEdge(0, -1));
//
EXPECT_TRUE(g.hasVertex(3));
EXPECT_TRUE(g.hasEdge(3, 100));
EXPECT_TRUE(g.removeEdge(3, 100));
EXPECT_FALSE(g.hasEdge(3, 100));
std::cout << g << '\n';
EXPECT_TRUE(g.removeVertex(3));
EXPECT_FALSE(g.hasVertex(3));
std::cout << g << '\n';
g.clear();
std::cout << g << '\n';
}
TEST(Dijkstra, solve_2)
{
DijkstraGraph<char, double> g0;
EXPECT_FALSE(g0.hasVertex(0));
EXPECT_FALSE(g0.hasVertex('B'));
EXPECT_FALSE(g0.hasVertex('s'));
EXPECT_FALSE(g0.hasEdge(0, 'B'));
EXPECT_FALSE(g0.hasEdge(0, 's'));
//
DijkstraSd dij;
DijkstraGraph<std::string, double> g;
EXPECT_THROW(dij.solve(g, "aaa", "bbb"), std::logic_error);
//
g.addVertex("aaa", "z", 100);
g.addVertex("aaa", "x", 100);
g.addVertex("z", "bbb", 200);
g.addVertex("x", "bbb", 10);
g.addVertex("bbb", "z", 1000);
std::cout << g << '\n';
EXPECT_EQ(4u, g.getSize());
double d = -1;
auto path = dij.solve(g, "aaa", "bbb", &d);
for (auto const& p : path) {
std::cout << p << '\n';
}
std::cout << "d: " << d << '\n';
EXPECT_EQ((std::vector<std::string>{ "aaa", "x", "bbb" }), path);
}
$ ./test/dijkstra.test
[==========] Running 2 tests from 1 test case.
[----------] Global test environment set-up.
[----------] 2 tests from Dijkstra
[ RUN ] Dijkstra.solve
-1
3
100
d: 31.23
(6) 7->7:0;; 5->7:2;; 0->3:200;0->-1:3.3;; -1->3:20;; 100->3:10;; 3->5:-10;3->100:11.23;;
-1
3
5
7
d: 12
-1
d: 0
7
d: 0
(6) 7->7:0;; 5->7:2;; 0->3:200;0->-1:3.3;; -1->3:20;; 100->3:10;; 3->5:-10;;
(5) 7->7:0;; 5->7:2;; 0->3:200;0->-1:3.3;; -1->3:20;; 100->3:10;;
(0)
[ OK ] Dijkstra.solve (1 ms)
[ RUN ] Dijkstra.solve_2
(4) x->bbb:10;; bbb->z:1000;; z->bbb:200;; aaa->x:100;aaa->z:100;;
aaa
x
bbb
d: 110
[ OK ] Dijkstra.solve_2 (0 ms)
[----------] 2 tests from Dijkstra (1 ms total)
[----------] Global test environment tear-down
[==========] 2 tests from 1 test cas