我理解Dijkstra的算法是什么,但我不明白为什么它的工作原理.
当选择下一个要检查的顶点时,为什么Dijkstra算法会选择权重最小的顶点？为什么不随意选择一个顶点,因为算法无论如何都会访问所有顶点？
Rex*_*err 23
您可以将Djikstra的算法视为一种注水算法(即修剪的广度优先搜索).在每个阶段,目标是以尽可能低的成本路径覆盖整个图表的更多部分.假设您在填充区域的边缘有顶点,并按距离列出它们:
v0 <= v1 <= v2 <= v3 ...
可能有更便宜的方式来到顶点v1吗？如果是这样,路径必须经过v0,因为没有未经测试的顶点可能更接近.因此,您检查顶点v0以查看可以到达的位置,检查是否有任何路径v0更便宜(距离任何其他顶点一步).
如果你以这种方式解决问题,你可以保证你的距离都是最小值,因为你总是检查那个可能导致最短路径的顶点.要么找到最短路径,要么排除它,然后继续前进到下一个顶点.因此,您可以保证每步消耗一个顶点.
并且你停止不做任何比你需要的工作,因为当你的目的地顶点占据"我是最小的" v0槽时停止.
我们来看一个简短的例子.假设我们正在试图从获取1到12的乘法和节点之间的成本是你必须乘以数量.(我们将顶点限制为从1到的数字12.)
我们从开始1,我们可以乘以该值到达任何其他节点.所以节点2有成本2,3有成本3,...... 如果你一步到位12就有成本12.
现在,通过路径2可以(在不知道结构)得到12最快的,如果有一个从免费链接2到12.没有,但如果有,它会是最快的.所以我们检查2.我们发现,我们可以得到4成本2,到6了3,等等.因此,我们有一个成本表,如下:
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.
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:
5 6 7 8 9 10 11 12
5 5 7 6 8 7 11 7
现在我们尝试5和6--no改善为止.这让我们失望了
7 8 9 10 11 12
7 6 8 7 11 7
现在,第一次,我们看到越来越到的成本8是少比让到的成本7,所以我们最好检查没有一些免费的方式去12从8.没有 - 根本没有办法到达整数 - 所以我们把它扔掉了.
7 9 10 11 12
7 8 7 11 7
现在我们看到它12和任何剩下的路径一样便宜,因此12必须达到成本7.如果我们一直跟踪到目前为止最便宜的路径(只有当它完全更好时才更换路径),我们会发现这3*4是第一个最便宜的方式12.
到目前为止,Dijkstra算法选择具有最小路径成本的顶点,因为通过任何其他顶点的路径至少与通过具有最小路径成本的顶点的路径一样昂贵.
因此,访问任何其他顶点,如果它更昂贵(这是非常可能的)将不仅需要访问其他顶点,而且还需要访问到目前为止路径成本最少的顶点,因此您必须在找到之前访问更多顶点最短路径.事实上, 如果你这样做,你最终会得到Bellman-Ford算法.
我还应该补充一点,顶点没有重量,它是有权重的边.给定顶点的关键是到目前为止从源顶点到该顶点的最短路径的成本.
| 归档时间： |
|
| 查看次数： |
8223 次 |
| 最近记录： |