Dijkstra的最短路径算法修改

我正在处理个人项目的图像，我卡在一个步骤（此外它是一个相对较简单的步骤）我的问题与图像的方式没有关系。Dijkstra的最短路径算法修改

我正在计算图像上每个像素的int值。我想找到像素（节点）之间成本最低的路径。其实我有一个A *算法的工作实现。但我不想使用它，因为我不想限制带有可以通过或不能通过的节点的“映射”。我希望每个节点都可以通过，但要付出代价。有些节点的成本过高，有些则不然。但是不会有无法通过的节点。

我不认为我需要给任何代码，因为它是一个非常孤立的项目的一部分。所以我不想操纵任何人。但基本上我有一个地图对象，有一个节点列表。节点有id，x，y位置。成本，邻居（顶部，底部，左侧和右侧像素）和一个节点参考知道我从哪里来到这里等。

我希望我能表达与Dijkstra的最短路径算法的区别。我怎样才能相应地修改它？或者有人可以推荐另一种方法来做到这一点？

来源

2012-04-18 user1125953

我不明白你为什么需要修改。 A *星和Dijkstra都有成本。有什么问题？ – Ishtar 2012-04-18 14:41:17

@Ishtar我认为在*中有2种节点。你可以通过的节点，你不能（墙壁）。我错了吗？对于Dijkstra的我不知道如何使用顶点和边。在我的情况下，它们都是同样的事情，一旦你通过一个节点，你就会将该节点的成本加到总成本中。 – user1125953 2012-04-18 19:24:16

我想我看到了这个问题..'有些节点的成本太高了，有些不会。这不是真的如何算法的工作，你应该把问题翻译成节点（没有成本）和边缘（与成本）。那么应该很容易使用A *，Dijkstra或任何其他寻路算法。

就你而言，每个像素都是一个节点/顶点。每个像素都有4条边（边界线除外）。边缘的成本将是目标像素的整数值。

另外，您不应该在节点中保留一个节点引用，这是算法工作来跟踪它来自哪里。

希望这会有所帮助。

来源

2012-04-18 20:57:56 Ishtar

谢谢。我不认为你喜欢，我认为算法可以适用于这种情况。我只是试图强调，总会有一条肯定的道路。我会给出相应的整数值，不用担心。在这个例子中，我没有看到seperatig节点和边的点。因为如果我这样实现，我认为边缘会非常混乱。因为让我们说x和y是2个节点。 x和y之间的边的成本必须不同于y和x之间的边的成本。如果你认为我无法理解你，请你尝试更多地解释它？ – user1125953 2012-04-18 21:25:58

我想你完全理解我。您必须做出选择，混淆边缘和众所周知的算法或对算法进行混淆修改。恕我直言，添加边缘，然后你不必担心算法是正确的。（有很多实现可用。） – Ishtar 2012-04-18 21:35:14

你能推荐我一个C＃实现？我找到了一个，但我认为这是有问题的:) – user1125953 2012-04-18 21:56:59

Dijkstra的最短路径算法修改

回答

相关问题