问题标签 [shortest-path]

我想知道如何为最短路径问题分配最大成本值。在我的问题中，我有与节点相关的风险。所以我想将风险降到最低，但同时我希望它找到一个节点数量有限的解决方案。（例如，找到从节点 A 到节点 B 的最小风险，同时确保解决方案不超过 n 个节点）谢谢很多。

我很难理解Johnson 算法的用处。我认为对于在这方面有知识的人来说，这个问题听起来一定很愚蠢，但我无法弄清楚。根据维基百科，约翰逊算法使用贝尔曼福特算法将边缘的权重转换为非负权重，然后使用 Dijkstra 算法找到最短路径。但贝尔曼福特算法也是一种寻找最短路径的算法。为什么我们不直接使用从贝尔曼福特算法中得到的最短路径？

我整天都在努力理解 Dijkstra 的算法并实施，但没有取得显著成果。我有一个城市及其距离的矩阵。我想要做的是给定一个起点和一个终点，找到城市之间的最短路径。

例子：

我开始想知道是否有其他方法可以解决这个问题。如果我从原点应用 Prim 算法，然后循环遍历创建的整个树，直到找到目标点会怎样？

我想写一个最短路径程序。我知道算法是如何工作的，但我不知道从哪里开始

最初，我想使用邻接矩阵，但后来因为空间问题决定放弃它。现在我认为邻接表会更好。

谁能建议我一个网站或教程如何开始编写邻接列表来为程序提供输入？

我知道标题有点乱，但我不知道如何更好地解释它。

我正在尝试做的事情：

使用在文本文件中找到的图，找到并打印从顶点 A 到顶点 B 的最短路径（最少顶点数）。

注意：使用广度优先搜索，而不是 Dijkstra 的。

我有什么：

一种在图上应用 BFS 的工作算法，但没有实际打印出最短路径的好方法。

我很难将最短路径中的顶点与仅通过算法运行但不在最短路径中的顶点区分开来。

例如：找到0和4之间的最短路径。0连接到1,2和3。1连接到4。我的路径结果是[0,1,2,3,4]而不是[0,1， 4]。

我还没有找到任何提出相同问题的线程，或者任何包含此问题的 BFS 演练，所以我不确定我是否让这变得比现在更难？

编辑：那些可能感兴趣的人的代码（完全不确定我是否要避免圈子？）

编辑 2：更改了将路径存储到堆栈的方式。

变量和方法的一些解释：

v = 原点

w = 目标顶点

g = 图表

vi = 迭代 v 的邻居的普通迭代器

谢谢阅读！

我需要租两间房子。我希望他们尽可能接近。大约有300间房屋可供出租。我希望使用 Google Maps Directions API 来计算任何两个可用房屋之间的步行距离，这样我就可以对列表进行排序并选择两个靠近的。

一切都很好，除了谷歌设定了每天 2,500 个查询的理论限制（实际上这个限制要低得多，每天只有 250 个）。我有 300 ² /2 - 300 = 44,700 个查询要进行，所以显然这个限制对我来说是不够的。

这将是一次性的，关于如何使用 Google Maps API 完成我需要的任何提示？我可以以某种方式运行分发的程序，这样限制只会影响一个实例吗？Google App Engine 会有所帮助吗？

我也欢迎改进算法的建议。如果两栋房子相距很远，而另一栋房子靠近其中一栋，则意味着它不必检查第三栋房子和剩下的房子，因为它们可能很远。我也更关心算法的定性性质，而不是确切的距离，所以也许我可以做出一个简单的近似来减少查询。

谢谢，

我已经实现了一个简单的 Dijkstra 算法，用于使用 Java 在 .osm 地图上查找最短路径。

从 .osm 文件创建的图中的路径查找工作得很好。但是如果用户的当前位置和/或目的地不是该图的节点（只是原始坐标），我们如何将这些坐标“链接”到图以进行寻路工作？

简单直接的解决方案“找到离当前位置节点最近的并画一条直线”似乎并不现实。如果我们遇到附图中的情况怎么办？(UPD)

这里的问题是，在我们开始任何“智能”寻路算法（如 Dijkstra 的）之前，我们将当前位置“链接”到图形，但这只是根据以下公式找到最近节点的愚蠢公式（勾股定理的斜边）地理坐标，这个公式不是“寻路”——它不能考虑障碍物和节点类型。

套用它 - 如果 B 是图中的节点，而 A 不是节点，我们如何找到 A 和 B 之间的最短路径？

你听说过这个问题的任何其他解决方案吗？

我有一个带有负边权重的有向图。图形被程序修改，有时会形成负循环。当这种情况发生时，最短路径算法（Bellman-ford/Johnson/Floyd-Warshall）会检测到这种负循环的存在并失败，但不会产生其他有用的信息。

我想确定是什么边导致了负循环，并不允许在图中进行此类修改。有人可以帮我指点吗？

谢谢，

保罗

您有一张方形瓷砖地图，您可以在其中向 8 个方向中的任何一个方向移动。假设你调用了一个函数cost(tile1, tile2)，它告诉你从一个相邻的瓦片移动到另一个瓦片的成本，你如何找到一个既可接受又一致的启发式函数 h(y,goal)？给定这个设置，寻找启发式的方法是否可以概括，或者它会根据cost功能而有所不同？

假设我有一个节点图（网络），权重如下： 1. 在两个节点之间的链接上单向行驶。2. 在两个节点之间的链接上以另一种方式行驶（这些可能不同）。3. 从一个链接更改为另一个链接。

此外，一些节点只是单向的。

在这种情况下，什么是最好的算法：a）找到最小生成树 b）找到两个节点之间的最短路径 c）找到“旅行推销员”路径（即，最短的路径去任何地方，重复最少） ?

另外，最好将双向事物视为两条单向路径，而不是在每个方向具有不同权重的双向路径？

- -一个例子 - -

其中 <2/3> 表示 2 左行和 3 右行的重量。^1/4 表示 1 上行和 4 下行。两个链接之间的单个数字是更改链接的成本 - 例如，从 AD 到 DF 成本为 8，从 AB 到 BE 成本为 2。

希望这是有道理的...

西蒙

（ps 为不好的术语道歉 - “链接”，“边缘” - 无论你喜欢什么;））

为了更好地解释权重类型，假设边缘是火车轨道，节点是车站。边缘的成本是火车在两个车站之间的行程时间，节点的成本是换乘时间的长短（即使在同一节点，边缘之间也可能有所不同，具体取决于站台的距离，服务的定期性等）。