gpt4 book ai didi

java - 适用于 500 多个航路点/节点的最短路径算法(例如 Dijkstra 算法)?

转载 作者:行者123 更新时间:2023-12-02 13:41:23 32 4
gpt4 key购买 nike

我在这里询问了最短路径算法: 2D waypoint pathfinding: combinations of WPs to go from curLocation to targetLocation

(要了解我的情况,请阅读该问题以及本问题。)

看来 Dijkstra 最短路径算法能够满足我的需要。但是,我的路线图中大约有 500 到 1000 个节点。

到目前为止,我所看到的实现将节点数量限制在 50 个以下。我的问题是:我是否仍然应该使用 Dijkstra 最短路径算法,或者其他替代方案? Java中有没有实现?

最佳答案

只有尝试过才知道。

1000 个节点实际上并不算多。 Dijkstra 算法在边的数量上具有线性复杂度,并且边的数量在最坏的情况下是节点数量的二次方。从您对图表的描述来看,很难判断有多少条边,但即使是完整的 1.000.000 也不是很大。

主要问题是您是否使用 priority queue 正确实现它.

编辑:Russell & Norvig ,第二版,在第 3 章和第 4 章中描述了一组通用搜索算法。他们所谓的统一成本图搜索本质上是 Dijkstra 算法。如果您按照他们的说明进行操作,则在需要时可以轻松地将算法扩展到 A* 搜索。

关于java - 适用于 500 多个航路点/节点的最短路径算法(例如 Dijkstra 算法)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5234557/

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