在Dijkstra算法中选择最近节点的意义是什么？
在Dijkstra算法中选择最近节点的意义是什么？
提问于 2020-01-23 04:33:18
在我读过的所有文章中，最先处理的邻居是“最近的”邻居。但最后需要访问所有节点，以找出所有可能的路径。所以，问题是-我们为什么要这样做？我相信，如果我们简单地以BFS方式遍历Graph，并进行成本计算，也可以达到同样的结果。例如：
第一步- 0，成本表:2-6|3-2
第二步- 2，成本表:2-6|3-2|1-9
第三步- 3，成本表:2-6|3-2|1-9|4- 12
第四步- 1，成本表:2-6|3-2|1-9|4- 12 |5- 12
第五步- 4，成本表:2-6|3-2|1-9|4- 12 |5- 12
通过简单的BFS遍历，找到了最便宜的方法。我错过了什么？
回答 2
Stack Overflow用户
回答已采纳
发布于 2020-01-23 05:48:04
假设从A到B和B到C的路径成本都是1，而从A到C的直接路径成本是3。(在现实世界中，前两条是绕过一座山的高速公路，而第三条是一条穿越山口的小路。)
Dijkstra将路由您的A -> B -> C，总成本为2，而BFS将路由您的A -> C，总成本为3。
因此，您必须首先处理最低成本，以获得正确的答案。
Stack Overflow用户
发布于 2020-01-23 07:26:05
在每一步，Dijkstra的算法扩展了到目前为止已知的最低成本路径。因此，当您最终遇到目标状态时，您知道所有其他未完成的路径具有更大的成本。因此，您刚刚找到的路径是最短路径。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/59867831
复制相关文章
相似问题
腾讯云开发者
