shortest-path 相关问题

最短路径问题是寻找从单个源到目标源的最短路径的问题，通常在图中。

使用 Boost 的 Dijkstra 最短路径实现查找一对顶点之间的多个（所有）最短路径

我一直在使用 Boost 使用 Dijkstra 最短路径算法 dijkstra_shortest_paths 的实现来查找图中两个节点之间的最短路径 (SP)。该函数返回一个

c++ shortest-path dijkstra boost-graph

回答 1 投票 0

如何加快 all_pairs_dijkstra_path_length

我有一个很大的 osmnx (networkx) 图，并且 nx.all_pairs_dijkstra_path_length 需要很长时间来计算。有哪些可能性可以加快计算速度？

python networkx shortest-path dijkstra osmnx

回答 2 投票 0

在C中使用BSF算法找到最短路径

我用C语言编写了使用BSF算法寻找最短路径的程序。下面是代码 #包括 #包括 #包括 #定义最大1000 国际分布...

c breadth-first-search shortest-path

回答 1 投票 0

我们可以使用BFS（以最优的方式）来找到带权有向无环图中从源节点到所有其他节点的最短路径吗？

我知道可以使用拓扑排序在 O(V+E) 内完成。但我认为使用 BFS 也可以以相同的复杂度完成。

graph-theory shortest-path breadth-first-search directed-acyclic-graphs topological-sort

回答 3 投票 0

在 Openlink Virtuoso 知识图中获取加权最短路径

上下文给定一个具有以下结构的 KG 3. 4. 背景给定一个具有以下结构的KG <distanceTo:1> <weight> 3 . <distanceTo:1> <weight> 4 . <a> <distance_with_weight> <distanceTo:1> . <distanceTo:1> <goes_to> <b> . <b> <distance_with_weight> <distanceTo:2> . <distanceTo:2> <goes_to> <c> . 我想说，a和c之间有一条路径，权重为3 + 4 = 7。问题有没有办法使用SPARQL或SPARQL-BI计算加权最短路径？我知道有 TRANSITIVE 和 T_SHORTEST 子句，但据我了解，它们仅适用于简单的边缘（没有权重）。我知道我可以枚举所有路径并取最小权重总和，但这是不可取的，因为在这种情况下，SSSP Dijkstra 算法可能会更快。到目前为止我所拥有的 SELECT ?t, total_weight WHERE { <a> <distance_with_weight>/<goes_to>* ?t. # here I need the sum of the weights involved so that I can get the minimum later. } 我不知道SPARQL-BI，所以也许有一个解决一般问题的方法，但是如果你的图是一棵树，也就是说，如果有一条从一个点到另一个点的唯一路径，那么纯SPARQL解决方案就可以工作。这个解决方案的部分灵感来自于Joshua Taylor对另一个问题的回答： PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#> SELECT ?destination (SUM(?weight) AS ?total_weight) WHERE { <a> (<distance_with_weight>/<goes_to>)*/<distance_with_weight> ?d . ?d <weight> ?weight . ?d <goes_to>/(<distance_with_weight>/<goes_to>)* ?destination . } GROUP BY ?destination 当图不是树（或森林）时，2个点之间可以存在多条路径，这样查询将添加所有路径的所有权重。循环也有问题，但最多不过是多条路径。最后，数据需要完整，为所有 <distanceTo:i> 节点分配权重，并且对于每对 (<a>,<b>)，必须有一个不同的 <distanceTo:i> 节点。

sparql shortest-path virtuoso

回答 1 投票 0

找到 NetworkX 中所有节点对之间的所有最短路径

我正在尝试获取无向未加权图中所有节点对之间的所有最短路径。我目前正在使用 nx.all_pairs_shortest_path()，但我不明白为什么它只返回一个

python python-3.x networkx graph-theory shortest-path

回答 4 投票 0

A* 曼哈顿距离

我搜索了A*的算法/伪代码，我按照它并编码了它。我使用曼哈顿距离作为 h(n)。 ( f(n) = g(n) + h(n) ) 而这就是结果，（来源：uploadir.com）这种事总是会发生

distance path-finding shortest-path a-star heuristics

回答 3 投票 0

最短路径 A* f(n) = g(n) + h(n)

当你使用A*时，它会选择最接近目标的最佳节点，对吗？（使用 f(n) = g(n) + h(n)）（使用 h(n) 的曼哈顿距离）但如果起点和……之间有墙怎么办