我正在尝试以一种有效的方式在 MySQL 数据库中存储超过 5GB 的未加权有向图，以找到最短路径。目前它存储在一个带有列源和一个列目标（逗号分隔）的表中，但我觉得这不是要走的路，所以我打算将它转换为一个带有顶点和一个表的表有边缘。
我有两个问题：
- 存储图表的最佳方式是什么？
- 我应该使用什么最短路径算法？
问问题
1379 次
2 回答
2
你应该有两张桌子。一个用于节点，一个用于边。在边表中，您应该有 source_node_id 和 dest_node_id。这样，您可以轻松地对边表进行查询，以获取 Dijkstra 算法使用的所有传出节点。
有关简单的 Dijksra 算法解释，请参见： http ://www.sce.carleton.ca/faculty/chinneck/po/Chapter8.pdf
于 2013-02-03T17:20:05.523 回答
0
存储密集图的另一种非常有效的方法（稀疏图不是那么有效）是使用邻接矩阵。这是一个解释它的链接 -
现在，要将矩阵存储在 MySQL 数据库中，您必须使用 rowid 作为行的顶点 id（假设您的顶点 id 为 1,2，...）。这些列可以只是普通的顶点名称或顶点 ID。您可以保留一个将顶点名称映射到 id 的表。
您将面临的一个问题是最大列数。如果您的矩阵太大，您可能必须将列拆分为多个表。如果您有一个索引方案/散列方案可以立即从您想要的节点告诉您表的名称，那么您的查询应该相对较快。
对于最短路径，正如其他人所提到的，Dijkstra 算法是目前最好的最短路径查找算法。
于 2015-07-06T12:48:03.780 回答