问题标签 [shortest]

除了 Dijkstra 之外，还有另一种方法可以计算接近完整图的最短路径吗？我有大约 8,000 个节点和大约 1800 万条边。我已经浏览了“地图上的 a 到 b”线程并决定使用 Dijkstra。我使用 Boost::Graph 库在 Perl 中编写了我的脚本。但结果不是我所期望的。使用调用 $graph->dijkstra_shortest_path($start_node,$end_node); 计算一条最短路径大约需要 10 多分钟。

我知道有很多优势，这可能是运行时间缓慢的原因。我死在水里了吗？有没有其他方法可以加快速度？

二维平面上有 n 个点。机器人想要访问所有这些，但只能水平或垂直移动。它应该如何访问所有这些以使其覆盖的总距离最小？

我在 mysql 中使用规范化邻接列表设计了一个加权图。现在我需要找到两个给定节点之间的最短路径。

我曾尝试在 php 中使用 Dijkstra，但我无法实现它（对我来说太难了）。我觉得另一个问题是，如果我使用 Dijkstra，我需要考虑所有节点，这在大图中可能效率很低。那么有人有与上述问题相关的代码吗？如果有人至少向我展示了解决这个问题的方法，那就太好了。我已经被困在这里将近一个星期了。请帮忙。

我正在解决一个问题，我需要在给定的有向未加权图中找到两个节点之间的所有最短路径。我已经使用 BFS 算法来完成这项工作，但不幸的是我只能打印一条最短路径而不是全部，例如，如果它们是 4 条长度为 3 的路径，我的算法只打印第一个但我希望它打印所有四个最短路径。我想知道在下面的代码中，我应该如何更改它以便可以打印出两个节点之间的所有最短路径？

我非常感谢您的大力帮助谢谢，安德拉

我发现许多算法和方法都在谈论寻找最短路径或问题的最佳/最佳解决方案。但是，我想做的是一种算法，它可以找到从一个点到另一个点的第一条 K 最短路径。我面临的问题更像是在树中搜索，当您采取的每一步都有多个选项时，每个选项都有其权重。什么样的算法用于面对这类问题？

我必须存储一些城市以及其中一些城市之间的距离，然后搜索最短路径。从文件中读取城市和距离。我从做一个矩阵开始，但发现它占用了太多空间（超过两倍），所以我改成了一个列表。每个列表项存储 3 个东西：point1、point2 和它们之间的距离。

所以例如我有这个文件：

雅典 斯德哥尔摩 34
斯德哥尔摩 布拉格 23

当我阅读时，它存储在数组中，如下所示：

然后我有一些疑问..这肯定会节省空间，但是否需要更多时间才能完成？该列表是一个数组，但连接（边）以任意方式放置，这就是为什么我开始认为它可能比使用矩阵需要更多时间。

这个程序应该返回二维数组中从左到右的最短路径的权重（它也可以越过顶部和底部，所以它就像一个水平圆柱体）。（这是一个完整的question_link）我是尝试通过首先向上，然后向右，最后在数组中向下递归检查。通过运行这个程序，如果我取消注释线的右方向和底部方向，我会得到“分段错误”。如果有人能告诉我我在递归函数中做错了什么。提前致谢！

在我的特定情况下，该图表示为邻接列表，并且是无向且稀疏的，n 可以以百万计，d 为 3。计算 A^d（其中 A 是邻接矩阵）并挑选出非零条目有效，但我想要不涉及矩阵乘法的东西。对每个顶点进行广度优先搜索也是一种选择，但速度很慢。

如何找到最短的字符串，它应该返回第一次出现

我有这个字符串。我正在寻找其值包含 blabla 并关闭 td 的 td。例如：

我只想要这个字符串

我在.net 中使用这个正则表达式

我是正则表达式的新手...

谁能告诉我出路。

我的 A* 算法实现需要一些帮助。当我运行算法时，它确实找到了目标，但路径肯定不是最短的：-P

这是我的代码，请帮我找出错误！我认为这可能是我的问题的重建路径，但我不确定。

}

感谢大家的所有伟大的答案！感谢你们，我的 A* 算法现在可以完美运行！:-)

这是我的第一篇文章，这个论坛真的很棒！