c++shortest-pathdijkstraboost-graph
Find multiple (all) shortest paths between a pair of vertices using Boost's Dijkstra shortest path implementation
I have been using Boost to find the shortest paths (SP) between two nodes in a graph using their implementation of Dijkstra's shortest path algorithm dijkstra_shortest_paths. This function returns a predecessor map that you can backtrack to get the SP from the target node. Despite this, the predecessor map does not account for the multiplicity of shortest paths.
I am calculating the shortest paths in a lattice (I know it is trivial but I need them for another thing) and my only option to get all the paths right now is to use Yen's algorithm. This solution is costly and, in theory, Dijkstra's algorithm is able to provide all SPs even with multiplicity. I saw this question but it is very old and maybe they have added some solution to the problem.
Does Boost have any solution for this?
Edit
Here is a sample code to calculate the SP using Dijkstra from boost:
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <fstream>
#include <boost/property_map/dynamic_property_map.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/tokenizer.hpp>
using namespace boost;
struct VertexProperties {
int custom_index;
};
typedef boost::adjacency_list<
boost::vecS, // OutEdgeList
boost::vecS, // VertexList
boost::undirectedS, // UnDirected
VertexProperties, // VertexProperties
boost::property<boost::edge_weight_t, double> // EdgeProperties
> Graph;
typedef graph_traits<Graph>::vertex_descriptor Vertex;// descriptors for vertices and edges in the graph, allowing easy access to graph elements.
typedef graph_traits<Graph>::edge_descriptor Edge;
typedef std::pair<Vertex, Vertex> EdgePair;// This represents an edge as a pair of integers (vertex indices).
typedef std::vector<Vertex> Path;
int main() {
/*
READING CSV FILE: EDGE[0], EDGE[1], WEIGHT
*/
Graph G(0);
std::ifstream file("graph.csv");
std::string line;
std::getline(file, line);
while (std::getline(file, line)) {
boost::tokenizer<boost::escaped_list_separator<char>> tokens(line);
auto tokenIterator = tokens.begin();
int vertex1 = std::stoi(*tokenIterator++);
int vertex2 = std::stoi(*tokenIterator++);
double weight = std::stod(*tokenIterator);
// Add edge to the graph with the given weight
Edge e = add_edge(vertex1, vertex2, G).first;
put(edge_weight, G, e, weight);
}
/*
END OF READ
*/
std::size_t numVertices = std::distance(boost::vertices(G).first, boost::vertices(G).second);
Path predecessors(numVertices);
std::vector<double> distances(numVertices);
dijkstra_shortest_paths(G, 0,
predecessor_map(make_iterator_property_map(predecessors.begin(), get(vertex_index, G)))
.distance_map(make_iterator_property_map(distances.begin(), get(vertex_index, G))));
// Reconstruct the Shortest path
std::vector<int> shortestP;
int currentNode = 80;
while (currentNode != 0) {
shortestP.push_back(currentNode);
if (predecessors[currentNode] == currentNode) {// target node not accessible
shortestP.clear();
break;
}
currentNode = predecessors[currentNode];
}
shortestP.push_back(0);
for (int i = 0; i < shortestP.size(); ++i) {
std::cout << shortestP[i];
if (i < shortestP.size() - 1) {
std::cout << " -> ";
}
}
}
This code reads a Graph from a csv file easily generated with networkx:
import csv
import networkx as nx
def write_graph_to_csv(G, filename = 'graph.csv'):
# Open a CSV file in write mode
with open(filename,
'w', newline='') as csvfile:
# Create a CSV writer object
csvwriter = csv.writer(csvfile)
# Write the header row (optional)
csvwriter.writerow(['vertex1', 'vertex2', 'edge_weight'])
# Write edges and their weights to the CSV file
for u, v, weight in G.edges(data='length'):
csvwriter.writerow([u, v, weight])
print('Graph has been written to graph.csv')
N = 9
graph = nx.grid_2d_graph(N,N,periodic=False)
pos = {i: j for i,j in enumerate(graph.nodes)}
labels = {i: k for k, i in enumerate(graph.nodes)}
nx.relabel_nodes(graph, labels, copy=False)
print(graph.nodes)
nx.draw_networkx(graph, pos, with_labels=True, node_size = 10)
edge_lens = {edge: np.linalg.norm(np.array(pos[edge[1]]) -
np.array(pos[edge[0]])) for edge in graph.edges}
nx.set_edge_attributes(graph, edge_lens, name = 'length')
write_graph_to_csv(graph)
The expected result would be all the shortest paths but I only get one:
Output:
80 -> 71 -> 70 -> 69 -> 68 -> 67 -> 58 -> 57 -> 56 -> 55 -> 54 -> 45 -> 36 -> 27 -> 18 -> 9 -> 0
Solution
Let's assume a sample directed graph
There are two paths from zero to three, having equal weight (1+5+7+3 == 1+12+3 == 16). However, the naive would only result in the first-discovered predecessor being recorded:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graphviz.hpp>
#include <fmt/ranges.h>
using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, struct VProps, struct EProps>;
using V = G::vertex_descriptor;
using Weight = double;
struct VProps { std::string name = "unnamed"; };
struct EProps { Weight weight = 0; };
void render(G& g) {
boost::dynamic_properties dp;
dp.property("node_id", get(&VProps::name, g));
dp.property("label", get(&EProps::weight, g));
dp.property("rankdir", boost::make_constant_property<G*>(+"LR"));
std::ofstream ofs("graph.dot");
write_graphviz_dp(ofs, g, dp);
system("/usr/bin/dot -Tpng -o dot.png graph.dot");
}
int main() {
G g(5);
auto vidx = get(boost::vertex_index, g);
auto name = get(&VProps::name, g);
auto weight = get(&EProps::weight, g);
name[0] = "A";
name[1] = "B";
name[2] = "C";
name[3] = "D";
name[4] = "E";
add_edge(0, 4, {1}, g);
add_edge(4, 1, {5}, g);
add_edge(4, 2, {12}, g);
add_edge(1, 2, {7}, g);
add_edge(2, 3, {3}, g);
render(g);
std::vector<Weight> dist(num_vertices(g));
std::vector<V> pred(num_vertices(g));
dijkstra_shortest_paths( //
g, 0, //
weight_map(weight) //
.distance_map(boost::make_iterator_property_map(dist.begin(), vidx)) //
.predecessor_map(boost::make_iterator_property_map(pred.begin(), vidx)) //
);
fmt::print("distances: {}\n", dist);
fmt::print("predecessors: {}\n", pred);
}
Printing
distances: [0, 6, 13, 16, 1]
predecessors: [0, 4, 4, 2, 0]
Tweaking The Predecessors
Now you can use the default distance recording, but you want to be smarter about the predecessors. You'd like to use e.g.:
std::vector<std::set<V>> pred(num_vertices(g));
That however doesn't work by default. So you can tweak it using your own visitor that records the predecessors instead:
struct vis_t : default_dijkstra_visitor {
state& s;
vis_t(state& s) : s(s) {}
void edge_relaxed(E e, G const& g) const {
s.pred[target(e, g)] = {source(e, g)};
}
void edge_not_relaxed(E e, G const& g) const {
// e: u -> v
auto u = source(e, g);
auto v = target(e, g);
auto old = s.dist[v];
auto new_ = s.dist[u] + g[e].weight;
if (std::nextafter(new_, old) == old) {
s.pred[v].insert(u);
}
}
} vis{s};
Note that comparison if floating point numbers is trickier, see How do you compare float and double while accounting for precision loss? and How to correctly and standardly compare floats?
Live Demo
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <fmt/ranges.h>
using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, struct VProps, struct EProps>;
using V = G::vertex_descriptor;
using E = G::edge_descriptor;
using Weight = double;
struct VProps { std::string name = "unnamed"; };
struct EProps { Weight weight = 0; };
int main() {
for (Weight alternative_weight : {6, 7, 8}) {
G g(5);
auto vidx = get(boost::vertex_index, g);
auto name = get(&VProps::name, g);
auto weight = get(&EProps::weight, g);
name[0] = "A";
name[1] = "B";
name[2] = "C";
name[3] = "D";
name[4] = "E";
add_edge(0, 4, {1}, g);
add_edge(4, 1, {5}, g);
add_edge(4, 2, {12}, g);
add_edge(1, 2, {alternative_weight}, g);
add_edge(2, 3, {3}, g);
struct state {
G& g;
std::vector<Weight> dist;
std::vector<std::set<V>> pred;
state(G& g) : g(g), dist(num_vertices(g)), pred(num_vertices(g)) {}
} s(g);
struct vis_t : boost::default_dijkstra_visitor {
state& s;
vis_t(state& s) : s(s) {}
void edge_relaxed(E e, G const& g) const {
s.pred[target(e, g)] = {source(e, g)};
}
void edge_not_relaxed(E e, G const& g) const {
// e: u -> v
auto u = source(e, g);
auto v = target(e, g);
auto old = s.dist[v];
auto new_ = s.dist[u] + g[e].weight;
if (std::nextafter(new_, old) == old)
s.pred[v].insert(u);
}
} vis{s};
dijkstra_shortest_paths( //
g, 0, //
weight_map(weight) //
.visitor(vis) //
.distance_map(make_iterator_property_map(s.dist.begin(), vidx)) //
);
fmt::print("distances: {}\n", s.dist);
fmt::print("predecessors: {}\n", s.pred);
}
}
Printing
distances: [0, 6, 12, 15, 1]
predecessors: [{}, {4}, {1}, {2}, {0}]
distances: [0, 6, 13, 16, 1]
predecessors: [{}, {4}, {1, 4}, {2}, {0}]
distances: [0, 6, 13, 16, 1]
predecessors: [{}, {4}, {4}, {2}, {0}]
Or with full event tracing Live On Coliru:
INIT A@0 , dist: [0 , 0 , 0 , 0 , 0 ], pred: [{}, {}, {}, {}, {}]
INIT B@0 , dist: [inf, 0 , 0 , 0 , 0 ], pred: [{}, {}, {}, {}, {}]
INIT C@0 , dist: [inf, inf, 0 , 0 , 0 ], pred: [{}, {}, {}, {}, {}]
INIT D@0 , dist: [inf, inf, inf, 0 , 0 ], pred: [{}, {}, {}, {}, {}]
INIT E@0 , dist: [inf, inf, inf, inf, 0 ], pred: [{}, {}, {}, {}, {}]
DISCOVER A@0 , dist: [0 , inf, inf, inf, inf], pred: [{}, {}, {}, {}, {}]
EXAMINE A@0 , dist: [0 , inf, inf, inf, inf], pred: [{}, {}, {}, {}, {}]
EXAMINE edge 0->4 weight 1
RELAXED edge 0->4 weight 1
DISCOVER E@1 , dist: [0 , inf, inf, inf, 1 ], pred: [{}, {}, {}, {}, {0}]
FINISH A@0 , dist: [0 , inf, inf, inf, 1 ], pred: [{}, {}, {}, {}, {0}]
EXAMINE E@1 , dist: [0 , inf, inf, inf, 1 ], pred: [{}, {}, {}, {}, {0}]
EXAMINE edge 4->1 weight 5
RELAXED edge 4->1 weight 5
DISCOVER B@6 , dist: [0 , 6 , inf, inf, 1 ], pred: [{}, {4}, {}, {}, {0}]
EXAMINE edge 4->2 weight 12
RELAXED edge 4->2 weight 12
DISCOVER C@13 , dist: [0 , 6 , 13 , inf, 1 ], pred: [{}, {4}, {4}, {}, {0}]
FINISH E@1 , dist: [0 , 6 , 13 , inf, 1 ], pred: [{}, {4}, {4}, {}, {0}]
EXAMINE B@6 , dist: [0 , 6 , 13 , inf, 1 ], pred: [{}, {4}, {4}, {}, {0}]
EXAMINE edge 1->2 weight 6
RELAXED edge 1->2 weight 6
FINISH B@6 , dist: [0 , 6 , 12 , inf, 1 ], pred: [{}, {4}, {1}, {}, {0}]
EXAMINE C@12 , dist: [0 , 6 , 12 , inf, 1 ], pred: [{}, {4}, {1}, {}, {0}]
EXAMINE edge 2->3 weight 3
RELAXED edge 2->3 weight 3
DISCOVER D@15 , dist: [0 , 6 , 12 , 15 , 1 ], pred: [{}, {4}, {1}, {2}, {0}]
FINISH C@12 , dist: [0 , 6 , 12 , 15 , 1 ], pred: [{}, {4}, {1}, {2}, {0}]
EXAMINE D@15 , dist: [0 , 6 , 12 , 15 , 1 ], pred: [{}, {4}, {1}, {2}, {0}]
FINISH D@15 , dist: [0 , 6 , 12 , 15 , 1 ], pred: [{}, {4}, {1}, {2}, {0}]
distances: [0, 6, 12, 15, 1]
predecessors: [{}, {4}, {1}, {2}, {0}]
INIT A@0 , dist: [0 , 0 , 0 , 0 , 0 ], pred: [{}, {}, {}, {}, {}]
INIT B@0 , dist: [inf, 0 , 0 , 0 , 0 ], pred: [{}, {}, {}, {}, {}]
INIT C@0 , dist: [inf, inf, 0 , 0 , 0 ], pred: [{}, {}, {}, {}, {}]
INIT D@0 , dist: [inf, inf, inf, 0 , 0 ], pred: [{}, {}, {}, {}, {}]
INIT E@0 , dist: [inf, inf, inf, inf, 0 ], pred: [{}, {}, {}, {}, {}]
DISCOVER A@0 , dist: [0 , inf, inf, inf, inf], pred: [{}, {}, {}, {}, {}]
EXAMINE A@0 , dist: [0 , inf, inf, inf, inf], pred: [{}, {}, {}, {}, {}]
EXAMINE edge 0->4 weight 1
RELAXED edge 0->4 weight 1
DISCOVER E@1 , dist: [0 , inf, inf, inf, 1 ], pred: [{}, {}, {}, {}, {0}]
FINISH A@0 , dist: [0 , inf, inf, inf, 1 ], pred: [{}, {}, {}, {}, {0}]
EXAMINE E@1 , dist: [0 , inf, inf, inf, 1 ], pred: [{}, {}, {}, {}, {0}]
EXAMINE edge 4->1 weight 5
RELAXED edge 4->1 weight 5
DISCOVER B@6 , dist: [0 , 6 , inf, inf, 1 ], pred: [{}, {4}, {}, {}, {0}]
EXAMINE edge 4->2 weight 12
RELAXED edge 4->2 weight 12
DISCOVER C@13 , dist: [0 , 6 , 13 , inf, 1 ], pred: [{}, {4}, {4}, {}, {0}]
FINISH E@1 , dist: [0 , 6 , 13 , inf, 1 ], pred: [{}, {4}, {4}, {}, {0}]
EXAMINE B@6 , dist: [0 , 6 , 13 , inf, 1 ], pred: [{}, {4}, {4}, {}, {0}]
EXAMINE edge 1->2 weight 7
NOTRELAXED edge 1->2 weight 7
ALTERNATIVE edge 1->2 weight 7
FINISH B@6 , dist: [0 , 6 , 13 , inf, 1 ], pred: [{}, {4}, {1, 4}, {}, {0}]
EXAMINE C@13 , dist: [0 , 6 , 13 , inf, 1 ], pred: [{}, {4}, {1, 4}, {}, {0}]
EXAMINE edge 2->3 weight 3
RELAXED edge 2->3 weight 3
DISCOVER D@16 , dist: [0 , 6 , 13 , 16 , 1 ], pred: [{}, {4}, {1, 4}, {2}, {0}]
FINISH C@13 , dist: [0 , 6 , 13 , 16 , 1 ], pred: [{}, {4}, {1, 4}, {2}, {0}]
EXAMINE D@16 , dist: [0 , 6 , 13 , 16 , 1 ], pred: [{}, {4}, {1, 4}, {2}, {0}]
FINISH D@16 , dist: [0 , 6 , 13 , 16 , 1 ], pred: [{}, {4}, {1, 4}, {2}, {0}]
distances: [0, 6, 13, 16, 1]
predecessors: [{}, {4}, {1, 4}, {2}, {0}]
INIT A@0 , dist: [0 , 0 , 0 , 0 , 0 ], pred: [{}, {}, {}, {}, {}]
INIT B@0 , dist: [inf, 0 , 0 , 0 , 0 ], pred: [{}, {}, {}, {}, {}]
INIT C@0 , dist: [inf, inf, 0 , 0 , 0 ], pred: [{}, {}, {}, {}, {}]
INIT D@0 , dist: [inf, inf, inf, 0 , 0 ], pred: [{}, {}, {}, {}, {}]
INIT E@0 , dist: [inf, inf, inf, inf, 0 ], pred: [{}, {}, {}, {}, {}]
DISCOVER A@0 , dist: [0 , inf, inf, inf, inf], pred: [{}, {}, {}, {}, {}]
EXAMINE A@0 , dist: [0 , inf, inf, inf, inf], pred: [{}, {}, {}, {}, {}]
EXAMINE edge 0->4 weight 1
RELAXED edge 0->4 weight 1
DISCOVER E@1 , dist: [0 , inf, inf, inf, 1 ], pred: [{}, {}, {}, {}, {0}]
FINISH A@0 , dist: [0 , inf, inf, inf, 1 ], pred: [{}, {}, {}, {}, {0}]
EXAMINE E@1 , dist: [0 , inf, inf, inf, 1 ], pred: [{}, {}, {}, {}, {0}]
EXAMINE edge 4->1 weight 5
RELAXED edge 4->1 weight 5
DISCOVER B@6 , dist: [0 , 6 , inf, inf, 1 ], pred: [{}, {4}, {}, {}, {0}]
EXAMINE edge 4->2 weight 12
RELAXED edge 4->2 weight 12
DISCOVER C@13 , dist: [0 , 6 , 13 , inf, 1 ], pred: [{}, {4}, {4}, {}, {0}]
FINISH E@1 , dist: [0 , 6 , 13 , inf, 1 ], pred: [{}, {4}, {4}, {}, {0}]
EXAMINE B@6 , dist: [0 , 6 , 13 , inf, 1 ], pred: [{}, {4}, {4}, {}, {0}]
EXAMINE edge 1->2 weight 8
NOTRELAXED edge 1->2 weight 8
FINISH B@6 , dist: [0 , 6 , 13 , inf, 1 ], pred: [{}, {4}, {4}, {}, {0}]
EXAMINE C@13 , dist: [0 , 6 , 13 , inf, 1 ], pred: [{}, {4}, {4}, {}, {0}]
EXAMINE edge 2->3 weight 3
RELAXED edge 2->3 weight 3
DISCOVER D@16 , dist: [0 , 6 , 13 , 16 , 1 ], pred: [{}, {4}, {4}, {2}, {0}]
FINISH C@13 , dist: [0 , 6 , 13 , 16 , 1 ], pred: [{}, {4}, {4}, {2}, {0}]
EXAMINE D@16 , dist: [0 , 6 , 13 , 16 , 1 ], pred: [{}, {4}, {4}, {2}, {0}]
FINISH D@16 , dist: [0 , 6 , 13 , 16 , 1 ], pred: [{}, {4}, {4}, {2}, {0}]
distances: [0, 6, 13, 16, 1]
predecessors: [{}, {4}, {4}, {2}, {0}]
- Why the first client seems to have source ip of 0.0.0.0?
- c - what is the most efficient way to copying a string?
- Why the linker cannot find my local C shared library for use with FFI in Rust?
- Linking with a custom-built pcc
- When does non-readable memory page happen?
- C printf() two strings on one line?
- Negative power of 2
- Use of goto to continue from several nested loops C
- Convert an int to ASCII character
- How to test a C pointer for whether it points to a struct
- is it good or bad to reuse the variables?
- How to trigger implicit pointer conversion inline in a C macro?
- How do I create a Virus signature?
- snprintf and sprintf explanation
- Code for implementing queue with ring buffer
- passing argument 2 makes pointer from integer without a cast
- How to declare a 2d Array without knowing the dimensions?
- what is the easiest way to read and process serial data for windows 32-bit systems?
- Where is SYSCALL() implemented in Linux?
- Does s conversion specifier specify direction / order in which characters are written?
- I'm getting an incredible error in the for loop in c language. For loop works in 1,2 and 3 but stops suddenly
- Address of local variable gives invalid address
- ESP-IDF linker not reporting duplicate functions so generating unsafe binary
- typedef for constant pointer to constant data function array
- Transfer pointer from dll (c/c++) to python
- Find out which thread/process is consuming CPU
- Chocolate Feast Program
- Embedding python in multithreaded C application
- C and C++ : Partial initialization of automatic structure
- How to access global variable via JNA interface?