在无向无权图中缓存 BFS 遍历
问题描述 投票：0回答：0
我有一个无向且未加权的图，其节点为 ~10^6 个节点 - 以矩阵格式可视化。 下图的示例表示。
红色格子被挡住了。
我的问题是找到最短距离 b/w 任何两个网格 - t源和目标网格将即时出现，在最坏的情况下 - 一个接一个 - 将询问所有对最短路径。
我试过 Floyd-warshall - 占用太多内存，所有节点的 dijkstra - 太慢了。
还有其他方法吗？ 由于它只是一个统一矩阵，我认为可能存在一些我不知道的模式。 这是否可以以某种方式缓存，以便已经遍历的 bfs 可以从中间点开始，而不是再次从头开始？
A* 可以工作但仍然很慢 - 如果需要找到所有对最短路径。
任何图书馆也会有帮助
最新问题
- git 正在尝试在 'git rebase --interactive <commit>'
- 如何卸载Docker或删除Docker目录？
- 使用 startAfter 检索数据时从 firestore 得到相同的响应
- 我不知道我遇到了什么错误..任何人都可以解释如何解决这个问题吗？
- MSVC++ 警告标志的 Wextra 替代方案
- 写入 STDOUT 时，Resque 作业失败并显示“Broken pipeline @ io_write - <STDOUT>”（Errno::EPIPE）
- Terraform 源代码中的两个斜杠如何工作？
- exec /usr/java/openjdk-20/bin/java：运行 docker 映像 AWS ECS fargate 时执行格式错误
- 防止 Kivy 留下调试消息
- 使用 flutter 在 iOS 应用程序中进行购买
- “函数是 Swift 中的一流类型”？
- 有办法解决这个错误信息吗？
- 列出 Python 3 中导入模块的导入模块
- 使用 Plotly Python 中的自定义模板创建具有不同颜色的堆叠条形图
- 如何使用 python 和 regulairexpressios 将所有数字替换为数字以外的东西？
- 如何在 VS Code 中设置键映射以遵循 Git Bash 终端快捷键并避免“等待和弦的第二个键”消息？
- Powershell 将一列列在另一列之上
- 为什么条件断点会使我的程序运行速度如此之慢？
- 如何将目录添加到 Poetry .venv 的 PATH 中？
- 如何在 Visual Studio Code 中使用 CMD-K 来清除我的终端？
© www.soinside.com 2019 - 2024. All rights reserved.