问题标签 [shortest-path]

我开始研究 Oracle 11g 空间数据库，我想知道是否有查询返回两点之间或点和线串之间的最短路径（或路径）。

我有一张带有一些线串（远足小径）和多边形（地理事故）的地图，我想在避免事故的同时找到我现在所在的位置和最近的小径之间的最短路线。我已经有一个查询返回最近的路径，但没有勾勒出事故的轮廓。

非常感谢你。

问题：在未加权的无向图中找到最短路径。

广度优先搜索可以找到两个节点之间的最短路径，但这可能需要 O(|V| + |E|) 时间。预先计算的查找表将允许在 O(1) 时间内回答请求，但代价是 O(|V|^2) 空间。

我想知道的是：是否有一种算法可以提供更细粒度的时空权衡？换句话说，是否有一种算法：

1. 在比 O(1) 更多的时间内找到最短路径，但比双向广度优先搜索更快
2. 使用比 O(|V|^2) 占用更少空间的预计算数据？

在实际方面：该图有 800,000 个节点，被认为是一个小世界网络。全对最短路径表的数量级为千兆字节——这在当今并不离谱，但它不符合我们的要求。

但是，出于好奇，我问我的问题。让我彻夜难眠的不是“我怎样才能减少所有对查找表的缓存未命中？”，而是“那里有我从未听说过的完全不同的算法吗？”

答案可能是否定的，没关系。

我想问一下是否有任何方法可以生成从节点 A 到节点 B 的最短路径，而无需在 QuickGraph 中使用 A-star 生成到所有其他节点的最短路径（当节点 B 在检查集中时停止）。

我想将 QuickGraph 插入游戏中，因此从环境施加的时间限制来看，不允许生成所有路径。

欢迎任何其他在 C# 中解决我的问题的建议

在此先感谢， Xtapodi

我有一个包含一些最短路径搜索算法的小型库。它们是为简单的无向图（正常表示 - 顶点和边）而开发的。现在我想以某种方式将它们应用到一个有点不同的场景中——地图被表示为二维形状，由共享边（即多边形的边）连接。在这种情况下，搜索可以在地图对象或某个点 (x,y) 开始/结束。最好的方法是什么？尝试将算法应用于形状？或尝试从形状中提取“正常”图形（我有可用的预处理时间）？任何建议将不胜感激，因为我真的不确定该走哪条路，而且我没有足够的时间（和技能）来探索许多选择......

非常感谢

我知道 R 是统计 pkg，但可能有库可以处理图形并找到 2 个节点的最短路径。

PS 实际上，我找到了 igraph 和 e1071，哪个更好？谢谢

我希望多个线程使用 BGL 的 dijkstra_shortest_paths 和 astar_search 函数，然后读取结果顶点和边的属性映射。

我想知道我是否应该使用互斥锁来确保线程安全。

所以这是我的问题：

1、Boost.Graph线程的dijkstra_shortest_paths和astar_search函数安全吗？

2.，如果我只尝试从多个线程读取图形的属性映射，我需要担心线程安全吗？

我有一个具有正边权重的有向无环图。它有一个源和一组目标（离源最远的顶点）。我找到从源到每个目标的最短路径。其中一些路径重叠。我想要的是一个最短路径树，它可以最小化所有边的权重总和。

例如，考虑两个目标。假设所有边权重相等，如果它们在大部分长度上共享一条最短路径，那么这比两条大多不重叠的最短路径更可取（树中的边越少，总成本越低）。

另一个例子：两条路径在它们的一小部分长度上不重叠，非重叠路径的成本高，但长共享路径的成本低（组合成本低）。另一方面，两条路径的大部分长度不重叠，非重叠路径的成本低，但短共享路径的成本高（同时，组合成本低）。有很多组合。考虑到从源到目标的所有最短路径，我想找到总成本最低的解决方案。

换句话说，我想要最短、最短的路径树。

这是否与任何人敲响了警钟？谁能指出我相关的算法或类似的应用程序？

干杯!

我需要在下图中计算从 A 到 B 的两条路径，约束条件是路径不能共享任何边：

嗯，好的，不能发图片，这是一个链接。

所有边都有正权重；对于这个例子，我认为我们可以假设它们是平等的。我天真的方法是使用 Djikstra 的算法来计算第一条路径，如上图的第二张图所示。

然后我从图中删除边并尝试计算第二条路径，但它失败了。是否有 Djikstra、Bellman-Ford（或其他任何东西）的变体可以计算上面第三张图中显示的路径？（没有特殊知识和删除对向链接，就是我的意思）

我正在寻找一种方法来实时找到巨大图中节点之间的最短路径。它有数十万个顶点和数百万条边。我知道以前有人问过这个问题，我想答案是使用广度优先搜索，但我更感兴趣的是知道你可以用什么软件来实现它。例如，如果它已经存在用于在无向图中执行 bfs 的库（带有 python 绑定！），那将是完全完美的。

我使用 JUNG API 计算中型大型图中（20 到 100 个节点）中几个节点之间的最短路径。现在我正在遍历我的节点并使用简单的“ShortetsPath”函数来计算两个节点的最短路径。所有最短路径都放在一个 ArrayList 中。

}

我想加快计算速度，因为我必须为许多图形和节点计算这个。据我所知，JUNG API 中只有 Dijkstra 可用。所以我的问题是：我可以使用 Dijkstra 来提高性能吗？JUNG API 中是否有其他算法可用？使用另一个为最短路径提供更多不同方法的图形实现是否有意义？

到目前为止感谢:)