Dijkstra算法是否需要检查所有顶点？

Question

3

我最近不得不研究Dijkstra算法及其证明。我在所有来源中找到的算法证明都以所有顶点数量和已访问顶点数量相等（例如R=V或S=V）结束。此外，该算法的while循环在Q（初始化为图的所有顶点）为空时终止，因此必须访问所有顶点。

我不明白为什么一定要这样。难道没有图形，算法不必访问所有顶点，例如：起始顶点直接连接到“查找”顶点，权重为1，并连接到其他顶点，权重为10。

我希望你能理解我的问题。

编辑：这是我从Cormen使用的伪代码。

- BenStudio

1

两个节点之间的最短路径算法会在到达目标节点时立即停止。也许您混淆了两个问题。 - user1196549

根据维基百科的说法，如果目标节点已被标记为访问过，则停止。 - Pham Trung

维基百科告诉我：“Dijkstra的最初变种找到了两个节点之间的最短路径，但更常见的变种将单个节点固定为“源”节点，并找到从源到图中所有其他节点的最短路径，生成一个最短路径树。” 你对哪种风格感兴趣？ - AakashM

1

这就是我的错误所在... 所以我面对的算法并不是寻找一个特定的节点，而是像你说的那样创建了一棵最短路径树... 好吧，这终于解决了我的问题。谢谢。 - BenStudio

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Beginner · Accepted Answer

Dijkstra算法通常用来计算从起始节点到所有相连节点的最短距离。即使在这种形式下，它也不会访问所有节点：只需检查一个连通分量的顶点即可。

对于两个节点之间的最短路径，有一种更有效的版本，可以在找到比迄今为止发现的最短路径更长的所有可能路径后停止搜索。该版本不总是访问连接子图的所有节点。