boost::graph::dijkstra_shortest_paths get edge information of path selected in graph with parallel edges

Previously boost::edge(v, u, graph) was sufficient with no parallel edges, but now it only seems to return the first edge encountered between the two vertices (always returns the first of parallel edges input to the graph).

Snippet of code where edge extraction is done (fg is a filtered version of a graph of type boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, Vertex, Edge>):

for (auto v : boost::make_iterator_range(vertices(fg)))
    {
        // Extract a shortest path
        typedef std::vector<edge_t> PathType;
        PathType path;
        vertex_t vv = v;
        for(vertex_t u = predecessors[vv]; 
            u != vv; // Keep tracking the path until we get to the source
            vv = u, u = predecessors[vv]
        ) // Set the current vertex to the current predecessor,     and the predecessor to one level up
        {
            // this is the problem. Need to pull the correct edge out of the graph using predecessor map
            std::pair<edge_t, bool> edgePair = boost::edge(u, vv, fg);
            edge_t edge = edgePair.first;
            path.push_back( edge );
        }

My goal is to get a std::vector<boost::graph_traits<graph_t>::edge_descriptor> object of the edges traversed by dijkstra_shortest_paths. predecessors is the predecessors map output from the algorithm.

Is there a simple way to do this that works for a graph with parallel edges?

So, given the predecessor-vertex map only, you have to iterate the out-edges of the predecessor and select the min-cost one.

If that sounds inefficient, don't worry: you were already doing exactly that, because edge(v,u,g) is only O(1) for AdjacencyMatrix models.

Here's a quick sketch:

for (V cur = v, p = predecessors[cur]; p != cur; cur = p, p = predecessors[cur]) {
    std::vector<E> candidates;
    for (E e : make_iterator_range(out_edges(p, g)))
        if (target(e, g) == cur)
            candidates.push_back(e);

    assert(!candidates.empty());
    auto best = *std::ranges::min_element(candidates, std::less<>{}, [wmap](E e) { return wmap[e]; });

    path.push_front(best);
}

Demo

Showing the correct path selection with various weights on the d and e parallel edges:

Live On Coliru

#include <boost/core/ignore_unused.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <fmt/ostream.h>
#include <fmt/ranges.h>
#include <ranges>

struct EdgeProps {
    std::string name;
    int         weight = 1;
};

using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, //
                                boost::no_property, EdgeProps>;
using V = G::vertex_descriptor;
using E = G::edge_descriptor;
using P = std::deque<E>;

template <> struct fmt::formatter<E> : ostream_formatter {};

void run(G const& g) {
    using boost::make_iterator_range;

    if (boost::num_vertices(g)==0)
        return;

    auto wmap          = get(&EdgeProps::weight, g);
    auto describe_edge = [&g](E e) { return g[e].name + ":" + std::to_string(g[e].weight); };

    std::vector<V>   predecessors(num_vertices(g));
    std::vector<int> distances(num_vertices(g));

    dijkstra_shortest_paths(                      //
        g, vertex(0, g),                          //
        weight_map(wmap)                          //
            .predecessor_map(predecessors.data()) //
            .distance_map(distances.data())       //
    );

    for (auto const v : make_iterator_range(vertices(g))) {
        P path;
        for (V cur = v, p = predecessors[cur]; p != cur; cur = p, p = predecessors[cur]) {
            std::vector<E> candidates;
            for (E e : make_iterator_range(out_edges(p, g)))
                if (target(e, g) == cur)
                    candidates.push_back(e);

            assert(!candidates.empty());
            auto best = *std::ranges::min_element(candidates, std::less<>{}, [wmap](E e) { return wmap[e]; });

            path.push_front(best);
        }

        if (v == 5)
            fmt::print("Path to {}: {::}\n", v, path | std::views::transform(describe_edge));
    }
}

int main() {
    G g;

    auto a = add_edge(0, 1, {"a"}, g).first;
    auto b = add_edge(1, 2, {"b"}, g).first;
    auto c = add_edge(2, 3, {"c"}, g).first;
    auto d = add_edge(3, 4, {"d"}, g).first;
    auto e = add_edge(3, 4, {"e"}, g).first;
    auto f = add_edge(4, 5, {"f"}, g).first;

    boost::ignore_unused(a, b, c, d, e, f);

    run(g);

    g[d].weight = 2; // favor e

    run(g);

    g[e].weight = 3; // favor d again

    run(g);
}

Which prints

Path to 5: [a:1, b:1, c:1, d:1, f:1]
Path to 5: [a:1, b:1, c:1, e:1, f:1]
Path to 5: [a:1, b:1, c:1, d:2, f:1]

Other Ideas

You might record edges instead of mere predecessors. That way you don't lose the information. For example, taking a slight variation on the example under "Quick Tour / Extending Algorithms with Visitors":

using PredEdges = std::vector<std::optional<E>>;
PredEdges predecessors(num_vertices(g));

auto predmap  = make_safe_iterator_property_map( //
    predecessors.begin(), num_vertices(g), get(boost::vertex_index, g));
using PredMap = decltype(predmap);

struct visitor_t : boost::default_dijkstra_visitor {
    PredMap pm;
    void edge_relaxed(E e, G const& g) const { put(pm, target(e, g), e); }
} vis{{}, predmap};

dijkstra_shortest_paths(g, vertex(0, g), weight_map(wmap).visitor(vis));

for (auto const v : make_iterator_range(vertices(g))) {
    P path;
    V cur = v;

    for (auto e = predecessors[cur]; e.has_value(); cur = source(e.value(), g), e = predecessors[cur])
        path.push_front(e.value());

    if (v == 5)
        fmt::print("Path to {}: {::}\n", v, path | std::views::transform(describe_edge));
}

Still prints the same output: Live On Coliru