问题标签 [shortest-path]

我将所有对最短路径算法（Floyd-Warshall）应用于此有向图：

该图由其邻接矩阵表示。简单的代码如下所示：

}

就算法而言，上述工作正常。

我试图表明从任何节点到自身的路径不一定是0，正如此处使用邻接矩阵所暗示的那样，但可以是通过其他节点的任何可能路径：例如B -...-...-...-B

有没有办法修改我当前的表示，以指示从 到 的最短路径B不是B零，而是12遵循该B-C-E-B路线？可以通过某种方式修改邻接矩阵方法来完成吗？

我知道有许多算法可用于计算图形或网格中两点之间的最短路径，例如广度优先、全对（Floyd's）、Dijkstra's。

然而，正如我所注意到的，所有这些算法都会计算该图形或网格中的所有路径，而不仅仅是我们感兴趣的两点之间的路径。

我的问题是： 如果我有一个网格，即一个二维数组，并且我有兴趣计算两点之间的最短路径，比如 P1 和 P2，以及我在网格上移动的方式是否受到限制（例如仅对角线，或仅对角线和向上等），什么算法可以计算这个？

请注意，如果您有答案，我希望您发布算法的名称而不是算法本身（当然，如果您也发布算法就更好了）；例如，无论是 Dijkstra 的算法，还是 Floyd 的算法，或者其他什么。

请帮助我，我已经考虑了几个月了！

伙计们，我在 TOPCODER.COM 上的网格中找到了这个算法，你只能移动（对角线和向上），但我不明白这是什么算法，任何人都知道吗？

我一直在为即将举行的编程比赛练习，我偶然发现了一个让我完全困惑的问题。然而，我觉得这是一个我现在应该学习的概念，而不是指望它永远不会出现。

基本上，它处理棋盘上的骑士棋子。您有两个输入：起始位置和结束位置。目标是计算并打印骑士到达目标位置的最短路径。

我从来没有处理过最短路径的事情，我什至不知道从哪里开始。我采用什么逻辑来解决这个问题？

PS如果有任何相关性，他们希望您通过允许骑士移动到由骑士可以进行的（可能）八个动作形成的广场的四个角落来补充骑士的正常动作，因为广场的中心是骑士的位置。

是否有一种算法或一组算法可以让您找到距任意起始节点的最短步行距离，以便在权重无向图中访问每个节点？它不完全是旅行推销员，因为我不在乎一个节点是否被多次访问。（即使你回到起点也没关系——只要它是访问所有节点所需的最后一个节点，walker 就可以最终到达某个遥远的节点。）它不是最小生成树，因为可能 A-->B-->C-->A-->D 是访问 A、B、C 和 D 的（非唯一）最短路径。我的直觉说这不是这不是一个 NP 问题，因为它没有使 NP 问题如此棘手的限制。当然，我可能完全错了。

我有大约 70k 个节点和 250k 个边，并且该图不一定是连接的。显然，使用有效的算法至关重要。你有什么建议吗？

作为旁注，我会很感激关于如何在多台机器之间划分任务的建议——这种问题甚至可能吗？

谢谢

这是一个我可以很容易地以非功能方式解决的问题。

但是在 Haskell 中解决它给了我很大的问题。我在函数式编程方面缺乏经验肯定是一个原因。

问题：

我有一个 2D 字段，分为大小相等的矩形。一个简单的网格。一些矩形是空的（可以通过），而另一些则无法通过。给定一个起始矩形A和一个目标矩形B，我将如何计算两者之间的最短路径？只能在垂直和水平方向移动，以单个矩形大的步骤进行。

我将如何在 Haskell 中完成此任务？代码片段当然受欢迎，但也肯定不是必需的。也非常欢迎提供更多资源的链接！

谢谢！

假设我有 10 分。我知道每个点之间的距离。

我需要找到通过所有点的最短路径。

我尝试了几种算法（Dijkstra，Floyd Warshall，...），它们都为我提供了起点和终点之间的最短路径，但它们并没有制定一条包含所有点的路线。

排列工作正常，但它们太耗费资源。

你能建议我研究什么算法来解决这个问题？或者是否有记录的方法可以使用上述算法来做到这一点？

我的代码中存在 turbo prolog 的问题，它在 2 个节点之间的图中搜索所有路径和最短路径。我遇到的问题是测试节点是否在列表中（正好在成员的子句中）

这是我的代码：

我试图在 Dijkstra 算法的 C 中理解这个实现，同时修改它，以便只找到 2 个特定节点（源和目标）之间的最短路径。

但是，我不知道该怎么做。在我看来，没什么可做的，我似乎无法更改d[]或prev[]导致这些数组聚合一些重要数据以进行最短路径计算。

我唯一能想到的就是在找到路径时停止算法，也就是说，mini = destination当它被标记为已访问时打破循环。

我还能做些什么来让它变得更好，或者这就足够了吗？

编辑：
虽然我很欣赏给我的建议，但人们仍然无法准确回答我的问题。我只想知道如何优化算法以仅搜索2 个节点之间的最短路径。目前，我对所有其他一般优化不感兴趣。我要说的是，在找到从节点 X 到所有其他节点的所有最短路径的算法中，如何优化它以仅搜索特定路径？

PS：我刚刚注意到for循环从1until开始<=，为什么它不能从0until开始<？

我有一个有向的正加权图。每个边缘都有使用成本。我只有 A 钱，我想用 dijkstra 算法计算最短路径，但路线上的边成本总和必须小于或等于 A。

我想用最小的 Dijstra 修改来做到这一点（如果我可以用 Dijkstra 的小修改来做到这一点）。如果可以的话，我必须这样做O(n*log(n))，但我想我可以。

任何人都可以帮助我吗？