Tag: 最短路径

所有对最短路径问题的最快实现？

我有一个加权图表30k节点160k边，没有负权重。 我想计算从所有节点到其他节点的所有最短路径。 我想我不能假设任何特定的启发式来简化问题。 我试图使用这个Dijkstra C实现http://compprog.wordpress.com/2007/12/01/one-source-shortest-path-dijkstras-algorithm/ ，这是针对单个最短路径问题，调用函数dijkstras （）我所有的30个节点。 你可以想象，它需要很长时间。 目前我没有时间自己编写和调试代码，我必须尽快计算这些路径并将它们存储在数据库中，这样我就可以找到另一个更快的解决方案了，你有没有有小费吗？ 我必须在最近的8GB内存的macbook pro上运行它，我想找到一个不超过24小时完成计算的解决方案。 非常感谢提前!! 欧亨尼奥

如何针对2个节点之间的单个最短路径优化Dijkstra算法？

我试图在Dijkstra算法的C中理解这个实现 ，同时修改它，以便只找到2个特定节点（源和目的地）之间的最短路径。 但是，我不确切知道该做些什么。 我看到它的方式，没有什么可做的，我似乎无法改变d[]或prev[]因为这些数组聚合了一些重要数据用于最短路径计算。 我唯一能想到的就是在找到路径时停止算法，也就是说，当mini = destination被标记为已访问时，打破循环。 还有什么我可以做的让它变得更好还是够了？ 编辑： 虽然我很欣赏给予我的建议，但人们仍未能完全回答我的质疑。 我想知道的是如何优化算法以仅搜索2个节点之间的最短路径。 到目前为止，我对所有其他一般优化都不感兴趣。 我所说的是，在找到从节点X到所有其他节点的所有最短路径的算法中，如何优化它以仅搜索特定路径？ PS：我刚注意到for循环从1开始直到<= ，为什么它不能从0开始直到< ？