如何用Boost的Dijkstra实现获取一对顶点间的所有最短路径？

我正在使用Boost的dijkstra_shortest_paths实现Dijkstra最短路径算法，用于查找图中一对节点间的最短路径。该函数返回的前驱映射仅能回溯得到目标节点的一条最短路径，无法处理存在多条最短路径的场景。

我需要在网格图（lattice）中计算所有最短路径，目前只能通过代价较高的Yen算法实现。理论上Dijkstra算法可支持获取所有最短路径，此前查阅过相关旧问题，想了解Boost当前是否有针对该需求的解决方案。

示例代码 #

C++读取图并计算单条最短路径 #

#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 << " -> ";
    }

}
}

Python（NetworkX）生成网格图CSV文件 #

import csv
import networkx as nx
import numpy as np

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)

当前输出与预期结果 #

当前运行仅能得到一条最短路径：

80 -> 71 -> 70 -> 69 -> 68 -> 67 -> 58 -> 57 -> 56 -> 55 -> 54 -> 45 -> 36 -> 27 -> 18 -> 9 -> 0

预期获取所有最短路径。

内容的提问来源于stack exchange，提问作者Robert Benassai