问题标签 [dijkstra]

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

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

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

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

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

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

我只是想确保这会奏效。你能找到使用 Dijkstra 算法的最佳路径吗？您是否必须先将距离初始化为-1，然后更改relax 子例程以检查它是否更大？

这是一个不会有任何负权重的问题。

这实际上是问题所在：

假设给定一个电话网络图，它是一个图 G，其顶点代表交换机中心，其边代表两个中心之间的通信线路。边缘由其最低带宽边缘的带宽标记。给出一个算法，给定一个图表和两个开关中心 a 和 b，将输出 a 和 b 之间路径的最大带宽。

这行得通吗？

编辑：

我确实找到了这个：

提示：基本子程序与 Dijkstra 中的 Relax 子程序非常相似。假设我们有一条边 (u, v)。如果 min{d[u],w(u, v)} > d[v] 那么我们应该将 d[v] 更新为 min{d[u],w(u, v)} （因为从 a 到u 然后到 v 的带宽为 min{d[u],w(u, v)}，比我们目前的带宽还要多）。

不完全确定这意味着什么，因为所有距离在初始化时都是无穷大的。所以，我不知道这将如何工作。任何线索？

我想不出一个具体的例子，在这种情况下你的体重是负的。你不能在两所房子之间有负距离，你不能及时回到过去。你什么时候会有一个负边权重的图？

我发现 Bellman Ford 算法最初用于处理 ARPANET 中的路由，但同样无法想象你会在哪里遇到负权重的路由，这似乎是不可能的。我可能只是想得太多了，一个简单的例子是什么？

正如标题所说，我正在尝试实现一种算法，找出给定图中所有节点对之间的距离。但还有更多：（可能对您有帮助的事情）

• 该图未加权。这意味着所有边缘都可以被认为具有权重 1。
• |E| <= 4*|V|
• 该图非常大（最多〜144深度）
• 图是有向的
• 可能有循环
• 我正在用python编写我的代码（如果你引用算法，代码也会很好:)）

我知道所有对的 Johnson 算法、Floyd-Warshal和Dijkstra。但是当图有权重时，这些算法很好。

我想知道是否有更好的算法适合我的情况，因为这些算法适用于加权图。

谢谢！

我正在尝试构建一个最短路径程序，但我对图表有疑问。你应该先画图？？？否则我将如何定义哪些节点是邻居？？？

在过去的几天里，我试图实现这个算法。到目前为止，我已经设法制作了一个动态二维数组并插入节点之间的距离，一个删除节点之间路径的函数以及一个告诉我两个节点之间是否存在路径的函数。现在我想实现一个函数，它返回从节点 A 到节点 B 的最短路径。我知道 dijkstras 算法是如何工作的，并且我已经阅读了 wiki 上的伪代码，但我自己却无法编写任何代码。我真的被困在这里了。

我一直在考虑代码应该是什么样子以及应该发生什么，这就是为什么我制作了那个告诉我两个节点之间是否有路径的函数。我是否需要更多帮助功能来简化 dijkstras 的实施？

目前我只有 3 个节点，但我想编写的代码通常需要适用于 n 个节点。

任何形式的帮助表示赞赏。

我一直在开发一个小程序，该程序使用 OpenMP 计算给定图中每个顶点的最短路径，以在多个线程之间拆分计算，而不是一次执行一个顶点。虽然我当前的实现有效，但我想这样做，以便我可以从格式为“vertex1 vertex2 weight”的文件中读取图形数据，这样图形就不会被硬编码到程序中。

来源在这里： http: //pastebin.com/bkR7QysB

编译如下：

使用以下数据作为输入：

我的输出是：

这显然是不正确的——它应该打印从一个顶点到图中每个其他顶点的最短路径，但在这里它只打印到自身的最短路径（始终为 0）以及到其直接相邻的一个的路径邻居。它根本没有遍历图表。然而，最奇怪的部分是取消注释 GraphTest.cpp 末尾附近的那个大块并注释掉文件处理代码，以便将图形数据硬编码到程序中，一切正常：

老实说，我不知道这里发生了什么。我唯一能想到的是某处的东西太早超出范围并导致我的图形对象行为异常，但如果这是真的那么两个输出应该是错误的......希望比我更聪明的人可以运行这并帮助我找出问题所在。

我们可以使用带有负权重的 Dijkstra 算法吗？

停止！在你认为“大声笑你可以在两点之间无休止地跳跃并获得一条无限便宜的路径”之前，我更多地考虑的是单向路径。

一个应用程序将是一个多山的地形，上面有点。显然从高到低并不消耗能量，事实上，它会产生能量（因此是负路径权重）！但是再回去是行不通的，除非你是查克·诺里斯。

我正在考虑增加所有点的权重，直到它们变为非负数，但我不确定这是否可行。

现在我想做的是，对于从 V1 到 V2 的每条边，我想设置 V2 到 V1 的距离（D）。如果 D 小于 V2 的当前距离，那么我们希望将 V2 的当前距离设置为 D，并将 V2 的前任设置为 V1。

我已将 V1 声明并初始化为最短距离（这只是初始点），并将其标记为完成。

问题：如何声明 V2 并设置它的距离？