algorithm - tutorial - floyd算法




为什么Dijkstra的算法有效? (5)

Dijsktra算法是一种贪婪算法,它遵循问题求解启发式,在每个阶段进行局部最优选择,希望找到全局最优。

我理解Dijkstra的算法是什么,但我不明白为什么它的工作原理。

当选择下一个要检查的顶点时,为什么Dijkstra算法会选择权重最小的顶点? 为什么不随意选择一个顶点,因为算法无论如何都会访问所有顶点?


Dijsktra算法的工作原理部分是因为它利用了包含点v节点uw之间的最短路径也包含从uv和从vw的最短路径的事实。 如果u到v之间存在较短的东西,那么它就不是最短的路径。

要真正理解Dijkstra算法的工作原理,请查看动态编程的基础知识,听起来很难,但理解原理非常容易。


到目前为止,Dijkstra算法选择具有最小路径成本的顶点,因为通过任何其他顶点的路径至少与通过具有最小路径成本的顶点的路径一样昂贵。

因此,访问任何其他顶点,如果它更昂贵(这是非常可能的)将不仅需要访问其他顶点,而且还需要访问到目前为止路径成本最少的顶点,因此您必须在找到之前访问更多顶点最短路径。 事实上,如果你这样做,你最终会得到Bellman-Ford算法

我还应该补充一点,顶点没有重量,它是有权重的边。 给定顶点的关键是到目前为止从源顶点到该顶点的最短路径的成本。


它喜欢贪婪的策略。我的英语不好。它是谷歌翻译的。如果你不明白,我很抱歉。

Dijkstra算法,从S到最短路径长度的所有顶点的G。 我们假设V中每个G的顶点都有一个标志L(V),它是一个数字,或者是∞。 假设P是G的顶点集合,P包含S,以满足:

A)如果V是P,那么从VS到最短路径长度的L(V),以及从S到最短路径的这种V的存在:P in中顶点上的路径

B)如果V不属于P,则从S到V的L(V)满足最短路径长度的以下限制:V是唯一路径P不属于顶点。

我们可以使用归纳来证明P Dijkstra算法符合上述集合的定义:

1)当P = 1中的元素数量时,P对应于算法中的第一步,显然满足P =(S)。

2)假设P是k,元素的数量,P满足上面的定义,参见第三步下面的算法

3)P in和第一个找出不标有最小顶点U,标记为L(U),可以证明从S到U的U在最短路径之外,除了P不包含元素之外不属于。

因为如果除了U之外还有其他顶点之外,则到S,P1,P2 ... Pn,Q1,Q2 ... Qn,U(P1,P2 ... Pn的最短路径是P; Q1,Q2, ...... Qn不属于P),从B)的性质来看,最短路径长度L(Q1)+ PATH(Q1,U)> L(U)。

哪个大于通道长度L(U)的S,P1,P2 ... Pn,U,不是最短路径。 因此,从最短路径的S到U的U,除了P不包含不属于U的元素从S到L(U)的最短路径的长度给出。

U以P'的形式添加到P中,显然是P'以满足A)的性质。

取V不属于P',显然不属于VP,那么从S到V除了最短路径并且满足路径中P'以外的所有顶点有两种可能性,i)包含U,ii)不包含U.

在i)S,P1,P2 ... Pn,U,V = L(U)+ W(U,V)

ii)S,P1,P2 ...... Pn,V = L(V)

显然,两个是从S中的最小V给出以满足最小访问,并且所有顶点的外部添加都是VP'的长度。

P'中给出的算法的第三步,用k + 1元素并满足A),B)。

通过归纳命题可能允许。

这是来源


您可以将Djikstra的算法视为一种注水算法(即修剪的广度优先搜索)。 在每个阶段,目标是以尽可能低的成本路径覆盖整个图表的更多部分。 假设您在填充区域的边缘有顶点,并按距离列出它们:

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

可能有更便宜的方式来到顶点v1 ? 如果是这样,路径必须经过v0 ,因为没有未经测试的顶点可能更接近。 因此,您检查顶点v0以查看可以到达的位置,检查通过v0任何路径是否更便宜(到一步之外的任何其他顶点)。

如果你以这种方式解决问题,你可以保证你的距离都是最小的,因为你总是检查那个可能导致最短路径的顶点。 要么找到最短路径,要么排除它,然后继续前进到下一个顶点。 因此,您可以保证每步消耗一个顶点。

并且你停止不做任何超出你需要的工作,因为当你的目的地顶点占据“我最小的” v0槽时停止。

我们来看一个简短的例子。 假设我们试图通过乘法从112 ,并且节点之间的成本是你必须乘以的数字。 (我们将顶点限制为112的数字。)

我们从1开始,我们可以乘以该值到达任何其他节点。 因此,节点2成本为2 ,成本为3 ,...如果您一步到位,则12成本为12

现在,如果有一个从212的免费链接,通过2的路径(不知道结构)可以达到最快12 。 没有,但如果有,它会是最快的。 所以我们检查2 。 我们发现,对于成本2 ,我们可以达到4 ,对于3可以达到6 ,依此类推。 因此,我们有一个成本表,如下:

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.

好的,现在也许我们可以从3免费获得12 ! 更好的检查。 我们发现3*2==6所以6的成本是32的成本, 9加3,12加4

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

很公平。 现在我们测试4 ,我们看到我们可以获得额外2 8 ,以及额外3 12 。 再次,达到12的成本因此不超过4 + 3 = 7

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

现在我们尝试56到目前为止没有改进。 这让我们失望了

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

现在,我们第一次看到,达到8的成本低于达到7的成本,所以我们最好检查一下,从8开始,没有一些免费的方法可以达到12 。 没有 - 根本没有办法实现整数 - 所以我们把它扔掉了。

7  9 10 11 12
7  8  7 11  7

现在我们看到12和任何路径一样便宜,所以达到12的成本必须是7 。 如果我们一直跟踪到目前为止最便宜的路径(只有当它完全更好时才更换路径),我们会发现3*4是第一个达到12最便宜的方式。







algorithm