0

我可以理解跟踪累积距离、每条路径的距离以及跟踪顶点的名称（或位置），但是为什么要跟踪步数，除非您想跟踪它到达目的地的效率?

这一步对于寻找路径是完全没有必要的，而且它似乎相当随意。例如，如果您有多个顶点，其中累积距离相同且数量最小，则没有理由关心您从哪个开始，但无论它是哪一个，都会被标记为下一步。

我看到很多代码，它们通常遵循跟踪步骤的原则。这似乎很奇怪，尤其是当他们中的许多人在移动成本为 1 或无限的 2D 矩阵上进行寻路时。在这种情况下，在我看来，不仅每个顶点的步数是多余的，而且唯一需要考虑的信息是顶点的距离和标签。如果你有一个距离，你就知道你已经访问了这个顶点，并且由于所有的距离都是相同的，你第一次到达一个顶点应该总是它的最低距离。没有必要评估它是更低还是更大，只要它存在即可。

无论如何，我只是好奇为什么这么简单的事情会收集到多余的信息。有什么原因我只是不明白吗？

编辑 -

为了增加一点清晰度，并且由于注释中的格式不正确，该步骤通常显示在人们告诉您使用的表格中。

____________________
|name|step|distance|
--------------------
|temporary Labels  |
--------------------

当某个位置是到原点的下一个最短点时，将添加该步长。

4

1 回答 1

2

好的，我现在已经看过那个视频了，这实际上是我第一次看到这样的桌子被使用。这对我来说没有多大意义。它将“标签”与“距离”完全混合在一起；永久标签是标记节点的顺序，而临时标签是当前的非固定距离。这些都不是必需的。

相反，您通常拥有的节点如下：距离（距起始节点）、父（或前一个）节点以及将节点标记为已完成或未完成的标记（在实现中，您通常有一个优先级队列代替所有未标记的节点）。

然后，您继续查看总距离最小的未标记节点，标记它并更新所有未标记邻居的距离。每当您更新到更短的距离时，您也会更新父节点。

无论如何，您都不需要将节点标记为已完成的顺序或具有所有先前未完成的距离。对我来说，在那个视频中，这似乎只是一种更容易检查学生作业的方法，因为没有相同的距离，你总是有一个单一的顺序来查看顶点。

话虽如此，普通的Dijkstra 算法不包括这些东西，也没有必要。有关您实际存储的内容的实现详细信息，请参见 Wikipedia 上的伪代码（如上所述，您通常只有每个节点的距离和父节点，以及未标记节点的优先级队列）。

这似乎很奇怪，尤其是当他们中的许多人在移动成本为 1 或无限的 2D 矩阵上进行寻路时。

你在这里描述的是一个非常特殊的情况。Dijkstra 算法实际上用于许多距离不相等的图问题，并且连接更多，每个方向只有 4 个简单的邻居。

于 2013-05-08T11:23:03.750 回答