了解Dijkstra算法 [英] Understanding Dijkstra Algorithm

问题描述

我试图理解Dijkstra算法以找到最短路径。

我想到了这个示例，其中顶层表格与图片相对应在左下角。

现在，我的问题是我不理解从步骤1到步骤2的过渡：

在UX中，我们可以通过将X的成本加V来转换为UXV （即2）到当前成本（即1； UX成本）。因此，总和为3，但由于这个数字大于我已经发现的2，所以我们不会对其进行更改。在第一步中，我们有两个成本都相同的选项。 UXY和UXV，但是为什么算法选择使用UXY而不是UXV？

请先感谢！

解决方案

当您有两个或两个以上的选项费用相同时，则继续进行选择不会有任何区别。 / p>

在 Dijkstra的算法维基百科文章包含用于执行该算法的伪代码的部分。您会看到，在伪代码中，Q中有一行 u←顶点，其行距为min dist [u] ，这意味着您选择了成本最低的一个选项。当您有更多相同价格的选择时，只需选择其中任何一个。

对于您的具体示例，这意味着您也可以使用UXV而不是UXY。 可能导致更多步骤，但是算法完成时最终结果是相同的。

I'm trying to understand the Dijkstra Algorithm for finding the shortest path.

I've came up to this example, where the top table corresponds to the image in the bottom left corner.

Now, my problem is that I don't understand the transition from step 1 to step 2:

When we are in UX we can travel to UXV by adding the cost of X to V (which is 2) to our current cost (which is 1; the cost of UX). So the sum would be 3, but since this I bigger then the 2 we already found we don't change it. In step 1 we have two options which both have the same cost; UXY and UXV, but why does the algorithm choose to go to UXY instead of UXV?

Thanks in advance!

解决方案

When you have two or more options with the same cost, it does not make any difference with which option you proceed.

In the Dijkstra's algorithm Wikipedia article there is a section with a pseudocode for implementing the algorithm. You can see that in the pseudocode there is a line u ← vertex in Q with min dist[u], which means that you choose one option with the lowest costs. When you have more options with the same cost, you just take any of those.

For your concrete example, this means that you could also go to UXV instead of UXY. This might lead to more steps, but the end result is the same when the algorithm finishes.

这篇关于了解Dijkstra算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！