在带有SQL的节点之间找到路径。

i have two mysql tables: nodes and relations

我有两个mysql表:节点和关系

CREATE TABLE `nodes` (
  `id` int(10) unsigned NOT NULL auto_increment,
  PRIMARY KEY  (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

CREATE TABLE `relations` (
  `node_id` int(10) unsigned NOT NULL,
  `related_node_id` int(10) unsigned NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

Lets say there are four rows in nodes: Node 1 and 2 share a relation, 2 and 3, 1 and 4, 4 and 3

假设节点中有4行:节点1和2共享一个关系，2和3、1和4、4和3。

INSERT INTO `relations` VALUES (1, 2);
INSERT INTO `relations` VALUES (2, 3);
INSERT INTO `relations` VALUES (1, 4);
INSERT INTO `relations` VALUES (4, 3);

Is there any algorithm to get the paths between the related nodes? Like

是否有算法来获取相关节点之间的路径?就像

+---------+------------------+---------+
| node_id | related_node_id  | route   |
+---------+------------------+---------+
|       1 |                2 | 1/2     |
|       2 |                3 | 2/3     |
|       1 |                4 | 1/4     |
|       4 |                3 | 4/3     |
|       1 |                3 | 1/2/3   |
|       1 |                3 | 1/4/3   |
+---------+-----------+------+---------+

2 个解决方案

#1

In vanilla MySQL, there is no easy way to do it.

在vanilla MySQL中，没有简单的方法。

You can install OQGRAPH (it's a plugin storage engine designed to store the graphs), create a graph table in it and issue a query like this:

您可以安装OQGRAPH(它是一个用于存储图的插件存储引擎)，在其中创建一个图表表并发出这样的查询:

SELECT  *
FROM    oqtable
WHERE   latch = 1
        AND origid = 1
        AND destid = 3

which will use Dijkstra's algorithm to find the shortest path between 1 and 3.

它将使用Dijkstra算法找到1到3之间的最短路径。

#2

I believe you are looking for the all-pairs shortest paths problem. SQL does not seem to be the right tool for solving this - lots of joins - therefore I suggest using a scripting language that interfaces with MySQL.

我相信你们在寻找全对最短路径问题。SQL似乎并不是解决这个问题的正确工具——很多连接——因此我建议使用与MySQL接口的脚本语言。

#1