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
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:
Live On Coliru
Printing
Tweaking The Predecessors
Now you can use the default
distancerecording, but you want to be smarter about the predecessors. You'd like to use e.g.:That however doesn't work by default. So you can tweak it using your own visitor that records the predecessors instead:
Live Demo
Live On Coliru
Printing
Or with full event tracing Live On Coliru: