Dijkstra、A* 与收缩层次
Dijkstra vs. A* vs. Contraction Hierarchies

原始链接: https://arcadedb.com/route-planning.html

来自9th DIMACS的佛罗里达路网:约107万个节点和约271万个路段,单位为公里/分钟。ArcadeDB路径规划用例通过一次GraphBatch请求在约11秒内加载它。Docker脚本启动数据库、加载数据、创建CCH视图并运行查询;Java示例运行相同查询,包括嵌入模式下在同一路径上比较Dijkstra、A*和CCH并应用交通拥堵。HTTP基准测试:从塔拉哈西到珊瑚阁,Dijkstra约3秒,A*约6秒,CCH约2毫秒。SQL函数遍历存储记录,而CCH使用内存层次结构;三者在同一视图上比较。文档涵盖最短路径选项和引擎识别。

Hacker News 新 | 过去 | 评论 | 提问 | 展示 | 工作 | 提交 登录 Dijkstra 与 A* 与 Contraction Hierarchies (arcadedb.com) 5 分 由 signa11 2 小时前 | 隐藏 | 过去 | 收藏 | 讨论 帮助 考虑申请 YC 的 Winter 2027 批次! 申请 开放至 11 月 2 日。 指南 | 常见问题 | 列表 | API | 安全 | 法律 | 申请 YC | 联系 搜索:
相关文章

原文

Everything on this page runs on the Florida road network of the 9th DIMACS Implementation Challenge: 1,070,376 junctions with their coordinates and 2,712,798 road segments with a length (km) and a travel time (minutes). The route-planning use case downloads it and loads it with one request to the GraphBatch endpoint, in about 11 seconds. With Docker:

git clone https://github.com/ArcadeData/arcadedb-usecases.git
cd arcadedb-usecases/route-planning
docker compose up -d     # starts ArcadeDB on port 2480
./setup.sh               # downloads Florida, loads it, creates the view with CCH (km, minutes)
./queries/queries.sh     # every query of this page, through curl

The java folder runs the same queries from a Java client, and embedded/FloridaRoutes.java runs them in an embedded database with no server and no build step: it loads the network with the GraphBatch Java API, compares dijkstra(), astar() and cchShortestPath() on the same route, shows the two costs, and applies the traffic jam.

java -Xmx4g -cp "$ARCADEDB_HOME/lib/*" embedded/FloridaRoutes.java

Through the HTTP API, Tallahassee to Coral Gables takes about 3 seconds with dijkstra(), 6 seconds with astar() and 2 milliseconds with cchShortestPath(). The SQL functions walk the stored records, while the hierarchy reads the in-memory view; the benchmark above compares all three on that same view. The Shortest Path guide covers every option, from the unweighted shortestPath() to A* heuristics, and how to check which engine answered a query.

联系我们 contact @ memedata.com