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

Question

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

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

我应该为 a) 空间效率 b) 时间效率使用什么表示和算法？

编辑：如果重要的话，

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

Answer 1

这取决于边缘的权重。如果它们是非负数 - Dijkstra适合您。如果您的图形是平面的，则可以使用A*。

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