问题标签 [dijkstra]

我想制作一个地图程序，为校园（宿舍、足球场等）和建筑物内（办公室、自助餐厅等）提供方向。是否存在任何有助于促进这一点的东西？

另一种选择似乎是我必须创建自己的校园周围点和路径的地图，并进行路径查找。

编辑：为了澄清，我想知道如何将空间意识添加到寻路程序中，以便为路径生成步行方向。示例：对于一个充满办公室的走廊，它有两个节点允许一条路径进入走廊，你怎么知道某个办公室是在一个节点的左边，另一个节点的右边？

Dijkstra 是最多产的计算机科学家之一。他写了著名的EWDs。将它们全部阅读是不可行的。但我认为有一些我们都必须阅读。

其中哪些是必读的？

我正在查看马里奥 AI 竞赛中的人一直在做什么，其中一些人利用 A*（A-Star）路径算法构建了一些非常简洁的马里奥机器人。

（马里奥 A* 机器人行动视频）

我的问题是，A-Star 与 Dijkstra 相比如何？看着它们，它们看起来很相似。

为什么有人会使用一个而不是另一个？尤其是在游戏路径的背景下？

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

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

在有效时间内找到通过图的最短路径，附加约束条件是路径必须恰好包含n 个节点。

我们有一个有向加权图。它可能包含也可能不包含循环。我们可以使用 Dijkstra 算法轻松找到最短路径，但 Dijkstra 不保证边数。

我们能想到的最好办法是保留一个节点的最佳 n 路径列表，但这比 vanilla Dijkstra 使用大量内存。

给定一个只有正边权重的有向连通图，是否有比使用斐波那契堆的 Dijkstra 更快的算法来找到两个顶点之间的最短路径？

维基百科说，Dijkstra 在 O(|E| + |V| * log(|V|)) 中（使用斐波那契堆）。

我不是在寻找例如一半执行时间的优化，而是在不同时间复杂度的算法（比如从 O(n * log n) 到 O(n)）。

此外，我想知道您对以下方法的看法：

1. 确定所有边权重的 GCD。
2. 将图转换为具有统一边权重的图。
3. 使用 BFS 找到两个给定顶点之间的最短路径。

第 2 点的示例：
想象 GCD 为 1。然后我将边缘
A--->B（边缘权重 3）
转换为
A->A'->A''->B（3 倍边缘权重 1）
这种转换需要固定的时间，并且必须为每条边完成一次。所以我希望这个算法在 O(|E|) (transformation) + O(|E| + |V|) (BFS) = O(2 * |E| + |V|) = O(|E|) + |V|)

感谢您花时间阅读我的问题，我希望没有浪费您的时间^^。祝你今天过得愉快。

有人可以提供使用银行家算法解决以下问题的逐步方法吗？如何确定是否存在“安全状态”？当一个过程可以“运行到完成”时意味着什么？

在此示例中，我有四个进程和 10 个相同资源的实例。

我想解决以下问题：

我有一个 DAG，其中包含需要完成的城市和工作。这些工作适用于可以装载定义限制的卡车。卡车装载的越多，旅行就越好。有些工作是为了加载一些东西，有些是为了加载定义的东西。即使他们之间没有工作要做，您也可以随时从城市 a 开车到 b。最后一个限制是我总是需要从 a 城市开始并返回 a，因为那里有卡车的家 :)

我首先想到的是 Dijkstra 的最短路径算法。我可以轻松地将其转换为最长路径计算。我现在想到的问题是，所有这些算法都用于计算从顶点 a 到 b 的最短或最长路径，但我需要它从 a 返回到 a - 在一个圆圈中。

有没有一些让我心动的？

感谢您的反馈意见！

马可

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

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

Dijkstra通常用于查找图中两个节点之间的最短距离。它可以用来找到最小生成树吗？如果是这样，怎么做？

编辑：这不是家庭作业，但我试图理解一个旧练习考试的问题。