I have a question regarding the edge weights when using Dijkstra's algorithm in Boost. The problem I am facing is that when the edge weights are large, I do not get a solution from Dijkstra's algorithm.
Let's say I have an adjacency list with bundled properties. My vertices are of type VertexType and edges are of type EdgeType. Here, VertexType resembles a person for a simple example. VertexType::pred is the predecessor when used with Dijkstra's algorithm.
struct VertexType
{
std::string name;
int age;
int pred;
};
struct EdgeType
{
double weight;
};
Below is a simple example.
void edgeWeightProblem()
{
// Graph and vertex descriptor typedefs.
typedef boost::adjacency_list<boost::vecS, boost::vecS,
boost::directedS,
VertexType,
EdgeType
> GraphType;
typedef boost::graph_traits<GraphType>::vertex_descriptor VertexDescriptor;
// Create graph and vertices vector.
GraphType G;
std::vector<VertexDescriptor> graphVertices;
// Add vertices.
graphVertices.push_back(add_vertex({"Tom", 23}, G));
graphVertices.push_back(add_vertex({"Frank", 25}, G));
graphVertices.push_back(add_vertex({"John", 42}, G));
graphVertices.push_back(add_vertex({"Emily", 22}, G));
// Add edges.
add_edge(graphVertices[0], graphVertices[1], {.2564}, G);
add_edge(graphVertices[0], graphVertices[2], {.3572}, G);
add_edge(graphVertices[1], graphVertices[3], {.1246}, G);
add_edge(graphVertices[2], graphVertices[3], {.5361}, G);
// Dijkstra shortest path.
dijkstra_shortest_paths(G, graphVertices.front(),
predecessor_map(boost::get(&VertexType::pred, G))
.distance_map(boost::get(&VertexType::pred, G))
.weight_map(boost::get(&EdgeType::weight, G)));
// Debug pred.
std::vector<VertexType> vec;
for (const VertexDescriptor& vd : graphVertices)
{
vec.push_back(G[vd]);
}
// Extract the shortest path.
std::vector<VertexDescriptor> shortestPath;
VertexDescriptor currentVertex = graphVertices.back();
while (currentVertex != graphVertices.front())
{
shortestPath.push_back(currentVertex);
currentVertex = G[currentVertex].pred;
}
shortestPath.push_back(currentVertex);
std::reverse(shortestPath.begin(), shortestPath.end());
// Display graph.
std::cout << "\nGraph Display: \n";
boost::print_graph(G);
std::cout << "\n";
// Print the shortest path.
std::cout << "Shortest Path: \n";
for (const auto& node : shortestPath)
{
std::cout << node << " -> ";
}
std::cout << "\n";
}
As expected, I get the following output:
Graph Display:
0 --> 1 2
1 --> 3
2 --> 3
3 -->
Shortest Path:
0 -> 2 -> 3 ->
But, if I remove the decimal of the edge weights, (ex: .2564 -> 2564), I will not be able to find the shortest path since the predecessor of each vertex will be itself. This also result in an infinite loop as a side affect for this example.
You can see this by placing a breakpoint after the "Debug pred" section and inspecting "vec". What is going on here? I assume this is a misunderstanding of Boost as I am quite new to it.
I have tried to play around with the weights, but it seems once the weights are larger, this issue happens. These weights are not so large that overflow should be a consideration, so I am quite confused as to what is happening.
CodePudding user response：
You're passing pred as both the predecessor map and the distance map. One will overwrite the other at unspecified points during algorithm execution. The result is unspecified at best, undefined if you're lucky.
Fixed that and simplified some of the code, now the result is the same for both weight inputs:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dag_shortest_paths.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iomanip>
#include <iostream>
struct VertexType {
std::string name;
int age;
size_t pred;
friend std::ostream& operator<<(std::ostream& os, VertexType const& vt) {
return os << "{" << std::quoted(vt.name) << ", " << vt.age << ", pred:" << vt.pred << "}";
}
};
struct EdgeType {
double weight;
};
int main() {
// Graph and vertex descriptor typedefs.
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, VertexType, EdgeType>;
using V = Graph::vertex_descriptor;
// Create graph and vertices vector.
Graph g;
// Add vertices.
V v0 = add_vertex({"Tom", 23, 0}, g);
V v1 = add_vertex({"Frank", 25, 0}, g);
V v2 = add_vertex({"John", 42, 0}, g);
V v3 = add_vertex({"Emily", 22, 0}, g);
// Add edges.
add_edge(v0, v1, {2564}, g);
add_edge(v0, v2, {3572}, g);
add_edge(v1, v3, {1246}, g);
add_edge(v2, v3, {5361}, g);
auto bundle = get(boost::vertex_bundle, g);
auto pred = get(&VertexType::pred, g);
auto weight = get(&EdgeType::weight, g);
auto distances = std::vector<double>(num_vertices(g));
// Dijkstra shortest path.
auto src = v0;
dijkstra_shortest_paths(g, src,
predecessor_map(pred)
.distance_map(distances.data())
.weight_map(weight));
#if 0
// Debug pred.
std::vector<VertexType> vertex_properties;
for (auto vd : boost::make_iterator_range(vertices(g))) {
vertex_properties.push_back(g[vd]);
}
#endif
// Extract the shortest path.
std::deque<V> path;
for (V cur = num_vertices(g) - 1;; cur = pred[cur]) {
path.push_front(cur);
if (cur == src || cur == pred[cur])
break;
}
// Display graph.
print_graph(g, bundle, std::cout << "Graph Display: \n");
// Print the shortest path.
std::cout << "\nShortest Path: ";
for (const auto& vd : path) std::cout << (vd == src ? "" : " -> ") << vd;
std::cout << "\nWhich is: ";
for (const auto& vd : path) std::cout << (vd == src ? "" : " -> ") << g[vd];
std::cout << "\n";
}
Prints
Graph Display:
{"Tom", 23, pred:0} --> {"Frank", 25, pred:0} {"John", 42, pred:0}
{"Frank", 25, pred:0} --> {"Emily", 22, pred:1}
{"John", 42, pred:0} --> {"Emily", 22, pred:1}
{"Emily", 22, pred:1} -->
Shortest Path: 0 -> 1 -> 3
Which is: {"Tom", 23, pred:0} -> {"Frank", 25, pred:0} -> {"Emily", 22, pred:1}