我应该使用哪种算法+表示法在巨大的稀疏无向图中找到最小路径距离？

Question

我需要找到无向图中两个节点之间的最小距离，这里有一些细节

• 该图无向且巨大（节点数量为 100,000 个）
• 图稀疏，边数小于节点数
• 我对实际路径不感兴趣，只对距离感兴趣。

我应该使用什么表示和算法来实现 a) Space 效率 b) 时间效率？

编辑：如果重要，

• 权重均为非零正整数
• 没有节点连接到自身。
• 两个相邻节点之间只有一条边

Answer 1

这取决于边的权重。如果它们是非负的 - Dijkstra suits you. If your graph is planar, you can use A*.

如果你有负权重，你必须使用Bellman-Ford。