使用 Boost 的 Dijkstra 最短路径实现查找一对顶点之间的多个（所有）最短路径
问题描述 投票：0回答：1
我一直在使用 Boost 通过 Dijkstra 最短路径算法的实现来查找图中两个节点之间的最短路径 (SP)
dijkstra_shortest_paths我正在计算格子中的最短路径（我知道这很简单，但我需要它们来做另一件事），而我现在获得所有路径的唯一选择是使用 Yen 算法。这种解决方案成本高昂，而且从理论上讲，Dijkstra 算法能够提供所有 SP，即使有重数也是如此。 我看到了这个问题，但它已经很老了，也许他们已经为问题添加了一些解决方案。
Boost 有解决方案吗？
编辑
这里是使用 boost 中的 Dijkstra 计算 SP 的示例代码：
#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 spur 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 << " -> ";
}
}
}
此代码从使用 networkx 轻松生成的 csv 文件中读取图表：
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)
预期的结果将是所有最短路径，但我只得到一条：
输出：
80 -> 71 -> 70 -> 69 -> 68 -> 67 -> 58 -> 57 -> 56 -> 55 -> 54 -> 45 -> 36 -> 27 -> 18 -> 9 -> 0
1个回答
0
投票
投票
我们假设一个有向图示例
有两条从零到三的路径，具有相同的权重（1+5+7+3 == 1+12+3 == 16）。然而，天真的只会导致第一个发现的前身被记录：
#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);
}
印刷
distances: [0, 6, 13, 16, 1]
predecessors: [0, 4, 4, 2, 0]
调整前辈
现在你可以使用默认的
distancestd::vector<std::set<V>> pred(num_vertices(g));
但是默认情况下这不起作用。因此，您可以使用记录前辈的您自己的访问者来调整它：
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)].insert(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};
请注意，如果浮点数比较比较棘手，请参阅如何在考虑精度损失的情况下比较 float 和 double？ 和 如何正确且标准地比较 float？
现场演示
#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() {
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);
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)].insert(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);
}
印刷
distances: [0, 6, 13, 16, 1]
predecessors: [{}, {4}, {1, 4}, {2}, {0}]
或者进行完整的事件追踪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 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}]
距离：[0, 6, 13, 16, 1] 前辈：[{}, {4}, {1, 4}, {2}, {0}]
最新问题
- 汉堡图标未显示
- 在 JPA 中使用与共享主键的一对一关系时出现重复条目
- axios调用可以处理不同的响应类型吗？
- 如何保护PostgREST免受sql注入和其他安全问题的影响？
- 找到最长字符串的索引并返回该索引
- npm run build:ci 中的 :ci 是做什么的？
- 如何使用 Spark 数据框架的架构创建 Hive 表？
- 准引用宏中的隐形模块函数
- javascript和html谷歌脚本删除谷歌表中的所有文本
- 错误：在 Angular Webpack 插件初始化之前尝试发出。在 npm start 上
- Xcode 15.2 缺少 iOS 17.2 设备支持
- Tweepy：Twitter 错误响应：状态代码 = 403：对 Azure 解决方案笔记本 (Spark) 中的推文提取进行故障排除
- 如何连接 Pandas 数据框中的特定行？
- 在最新的jupyter笔记本中使用神奇的matplotlib函数
- Bash 函数从 POSIX PATH 中删除重复项
- 使用单个函数按 ID 对多个表进行排序
- 最小日期和最大日期不起作用角度材料范围输入
- 如何在命令提示符下获取最近 30 分钟的 CloudWatch Logs？
- Elasticsearch - 从 Java High Level Rest 客户端迁移到版本 8.x 的新 Java API 客户端
- 我如何整合whatsapp APi
© www.soinside.com 2019 - 2024. All rights reserved.