为什么Dijkstra的算法有效？ [英] Why does Dijkstra's algorithm work?

问题描述

我了解 Dijkstra的算法是，但是我不明白它为什么起作用。

I understand what Dijkstra's algorithm is, but I don't understand why it works.

在选择下一个要检查的顶点时，为什么Dijkstra的算法选择具有最小的重量？为什么算法不访问所有顶点，为什么不随便选择一个顶点呢？

When selecting the next vertex to examine, why does Dijkstra's algorithm select the one with the smallest weight? Why not just select a vertex arbitrarily, since the algorithm visits all vertices anyway?

推荐答案

您可以将Djikstra的算法视为注水算法（即修剪的广度优先搜索）。在每个阶段，目标都是以尽可能最低的成本覆盖整个图表。假设您在所填充区域的边缘有顶点，并按距离列出了它们：

You can think of Djikstra's algorithm as a water-filling algorithm (i.e. a pruned breadth-first search). At each stage, the goal is to cover more of the whole graph with the lowest-cost path possible. Suppose you have vertices at the edge of the area you've filled in, and you list them in terms of distance:

v0 <= v1 <= v2 <= v3 ...

是否有可能更便宜到达顶点 v1 的方法？如果是这样，路径必须经过 v0 ，因为没有未经测试的顶点可以更近。因此，您检查顶点 v0 以了解到达的位置，并检查通过 v0 的路径是否便宜（

Could there possibly be a cheaper way to get to vertex v1? If so, the path must go through v0, since no untested vertex could be closer. So you examine vertex v0 to see where you can get to, checking if any path through v0 is cheaper (to any other vertex one step away).

如果以此方式消除问题，则可以确保距离都是最小的，因为您始终会准确地检查那个顶点可能会导致最短的路径。找到最短路径，或者排除最短路径，然后移至下一个顶点。因此，您可以确保每步消耗一个顶点。

If you peel away the problem this way, you're guaranteed that your distances are all minimums, because you always check exactly that vertex that could lead to a shortest path. Either you find that shortest path, or you rule it out, and move on to the next vertex. Thus, you're guaranteed to consume one vertex per step.

您可以停止而不做任何多余的工作，因为当目标顶点占据了顶点时，您就停止了我是最小的 v0 插槽。

And you stop without doing any more work than you need to, because you stop when your destination vertex occupies the "I am smallest" v0 slot.

让我们看一个简单的示例。假设我们正试图通过乘法从 1 到 12 ，并且节点之间的成本就是您拥有的数量乘以。 （我们将顶点限制为从 1 到 12 的数字。）

Let's look at a brief example. Suppose we're trying to get from 1 to 12 by multiplication, and the cost between nodes is the number you have to multiply by. (We'll restrict the vertices to the numbers from 1 to 12.)

我们从 1 开始，然后乘以该值即可到达任何其他节点。因此节点 2 的成本为 2 ， 3 的成本为 3 ，... 12 如果您去，则花费了 12

We start with 1, and we can get to any other node by multiplying by that value. So node 2 has cost 2, 3 has cost 3, ... 12 has cost 12 if you go in one step.

现在，通过 2 的路径可以（不知道结构）达到<$如果存在从 2 到 12 的免费链接，则c $ c> 12 最快。没有，但是如果有，那将是最快的。因此，我们检查 2 。而且我们发现我们可以以成本 2 达到 4 ，达到 6 表示 3 ，依此类推。因此，我们有一个这样的成本表：

Now, a path through 2 could (without knowing about the structure) get to 12 fastest if there was a free link from 2 to 12. There isn't, but if there was, it would be fastest. So we check 2. And we find that we can get to 4 for cost 2, to 6 for 3, and so on. We thus have a table of costs like so:

3  4  5  6  7  8  9 10 11 12 // Vertex
3  4  5  5  7  6  9  7 11  8 // Best cost to get there so far.

好的，现在也许我们可以达到 12 免费从 3 开始！更好地检查。我们发现 3 * 2 == 6 ，所以 6 的成本就是 3 加 2 ，而 9 加 3 和 12 加上 4 。

Okay, now maybe we can get to 12 from 3 for free! Better check. And we find that 3*2==6 so the cost to 6 is the cost to 3 plus 2, and to 9 is plus 3, and 12 is plus 4.

4  5  6  7  8  9 10 11 12
4  5  5  7  6  6  7 11  7

足够。现在我们测试 4 ，我们看到可以得到 8 额外的 2 ，并添加到 12 额外的 3 。同样，达到 12 的成本不超过 4 + 3 = 7 ：

Fair enough. Now we test 4, and we see we can get to 8 for an extra 2, and to 12 for an extra 3. Again, the cost to get to 12 is thus no more than 4+3 = 7:

5  6  7  8  9 10 11 12
5  5  7  6  8  7 11  7

现在我们尝试 5 和 6 -到目前为止没有任何改进。

Now we try 5 and 6--no improvements so far. This leaves us with

7  8  9 10 11 12
7  6  8  7 11  7

现在，我们第一次看到达到 8 比获得 7 的成本要少 ，因此我们最好检查一下是否没有免费的方式获得<$ c c $ c> 12 来自 8 。没有-用整数根本无法到达那里-所以我们把它扔掉了。

Now, for the first time, we see that the cost of getting to 8 is less than the cost of getting to 7, so we had better check that there isn't some free way to get to 12 from 8. There isn't--there's no way to get there at all with integers--so we throw it away.

7  9 10 11 12
7  8  7 11  7

现在我们看到 12 与剩下的任何路径一样便宜，因此达到 12 的成本必须为 7 。如果我们到目前为止一直跟踪最便宜的路径（仅在严格改善的情况下才替换路径），我们会发现 3 * 4 是第一种最便宜的方法点击 12 。

And now we see that 12 is as cheap as any path left, so the cost to reach 12 must be 7. If we'd kept track of the cheapest path so far (only replacing the path when it's strictly better), we'd find that 3*4 is the first cheapest way to hit 12.

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