Dijkstras算法似乎没有工作，我的理解必须是有缺陷 [英] Dijkstras Algorithm doesn't appear to work, my understanding must be flawed

问题描述

下面是Dijkstra算法我跨pretation所描述的维基百科会处理如下图。

首先，它标志着到所有相邻节点的最短距离，因此得到1和C得到7.然后选取当前最短路径的邻居。这是A的原点被标记为已访问和将不再次考虑。最短（也是唯一）从通过到B的来源路径，现在12，被标记为已访问。从产地到到B目的地的最短路径是13. B被标记为已访问。从通过目的地的来源为C的最短路径是14，但是这是双重的previous最短路径C，它是7，所以14被丢弃。目标现在被标记为已访问。

目标已被标记访问，因此算法FFT完成。这里的结果是：

我也是misinter pretting的描述？是维基百科的描述错了吗？还是我莫名其妙地偶然发现，显示Dijkstra算法是不正确（我很怀疑）的情况？我注意到，所选择的路径似乎在贪婪方式被拾取，但显然这是该算法的特征之一，但是在这种情况下，它似乎给错误的结果。

解决方案

  

    

分配给每个节点一个试探性的距离值：设置为零，为我们的初始节点和无限的所有其他节点。标记所有节点未访问。设置初始节点的电流。创建一组被称为未访问的集合组成，除了初始节点的所有节点的未访问节点。 （维客）

  

使用你的例子：

未访问

  A = INF;
B = INF;
C = INF;
目的地= INF;
 

访问

 产地= 0;
 

有关当前节点，考虑其所有未访问的邻居，并计算它们的暂行距离。

  O =＆GT; A = 1;
O =＆GT; C = 7;
 

我们现在正处于一个。

从A，唯一的路径是B，这给了我们

  O =＆GT; AB = 12;
O =＆GT; C = 7
 

C是现在最低距离，并且是新的当前节点

  O =＆GT; CD = 8
 

由于D为目的地和8示12，路线CD被选择

Here's my interpretation of how Dijkstra's algorithm as described by wikipedia would deal with the below graph.

First it marks the shortest distance to all neighbouring nodes, so A gets 1 and C gets 7. Then it picks the neighbour with the current shortest path. This is A. The origin is marked as visited and will not be considered again. The shortest (and only) path from the origin to B through A is now 12. A is marked as visited. The shortest path from the origin to the Destination through B is 13. B is marked as visited. The shortest path from the Origin to C through the destination is 14, but this is double the previous shortest path to C, which is 7, so the 14 is discarded. The destination is now marked as visited.

Destination has been marked visited, therefore the alogorithm is complete. Here's the result:

So am I misinterpretting the description? Is the description on wikipedia wrong? Or have I somehow stumbled upon a case that shows Dijkstra's algorithm is incorrect (which I highly doubt)? I've noticed that the path chosen seems to be picked in a greedy manner, but apparently this is one of the defining characteristics of the algorithm, however in this case it seems to give the wrong result.

解决方案

Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes. Mark all nodes unvisited. Set the initial node as current. Create a set of the unvisited nodes called the unvisited set consisting of all the nodes except the initial node. (Wiki)

Using your example:

Unvisited

A = inf;
B = inf;
C = inf;
Dest = inf;

Visited

Origin = 0;

For the current node, consider all of its unvisited neighbors and calculate their tentative distances.

O => A = 1;
O => C = 7;

We are now at A.

From A, the only path is B, this gives us

O => AB = 12;
O => C = 7

C is now lowest distance, and is the new current node

O => CD = 8

Since D is destination and 8 < 12, the route CD is chosen.

这篇关于Dijkstras算法似乎没有工作，我的理解必须是有缺陷的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！