gpt4 book ai didi

algorithm - Dijkstra 如何找到这个图中的最短路径?

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:40:45 24 4
gpt4 key购买 nike

如果我们必须找到从 0 到 3 的最短路径,我很难理解 Dijkstra 如何在下图中找到最短路径(从我理解它的工作方式):https://graphonline.ru/tmp/saved/SH/SHBqKyENwJqcCJGM.png

如果算法从0中选择最小的权值,并标记0为已访问,那么它不会先选择节点1再选择节点3吗?它会如何选择节点 2?

最佳答案

Dijkstra 算法涉及一个优先级队列,其中保留了从被访问节点可直接到达的所有节点,以及它们到起始节点的距离。

该算法将访问节点 0,并将节点 1 和 2 添加到优先级队列中。然后它将访问节点 1,因为它是优先级队列中最近的节点,并将节点 3 添加到优先级队列中,距离为 6。节点 2 仍在队列中,因为它比节点 3 更靠近节点 0 ,接下来会访问它。当访问节点2时,会找到到节点3的长度为4的较短路径,因此到节点3的距离将更新为4。然后访问节点3。

关于algorithm - Dijkstra 如何找到这个图中的最短路径?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56615632/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com