java - 为最短路径计算存储一个巨大的图表

Question

我正在尝试以一种有效的方式在 MySQL 数据库中存储超过 5GB 的未加权有向图，以找到最短路径。目前它存储在一个带有列源和一个列目标（逗号分隔）的表中，但我觉得这不是要走的路，所以我打算将它转换为一个带有顶点和一个表的表有边缘。

我有两个问题：

1. 存储图表的最佳方式是什么？
2. 我应该使用什么最短路径算法？

Answer 1

你应该有两张桌子。一个用于节点，一个用于边。在边表中，您应该有 source_node_id 和 dest_node_id。这样，您可以轻松地对边表进行查询，以获取 Dijkstra 算法使用的所有传出节点。

有关简单的 Dijksra 算法解释，请参见： http ://www.sce.carleton.ca/faculty/chinneck/po/Chapter8.pdf

Answer 2

存储密集图的另一种非常有效的方法（稀疏图不是那么有效）是使用邻接矩阵。这是一个解释它的链接 -

使用邻接矩阵存储图

现在，要将矩阵存储在 MySQL 数据库中，您必须使用 rowid 作为行的顶点 id（假设您的顶点 id 为 1,2，...）。这些列可以只是普通的顶点名称或顶点 ID。您可以保留一个将顶点名称映射到 id 的表。

您将面临的一个问题是最大列数。如果您的矩阵太大，您可能必须将列拆分为多个表。如果您有一个索引方案/散列方案可以立即从您想要的节点告诉您表的名称，那么您的查询应该相对较快。

对于最短路径，正如其他人所提到的，Dijkstra 算法是目前最好的最短路径查找算法。