查找节点之间的路径与SQL

Question

我有两个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; 

比方说，有四行中的节点：节点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); 

是否有任何算法来获取相关节点之间的路径？像

+---------+------------------+---------+ 
| 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 | 
+---------+-----------+------+---------+ 

Answer 1

我相信你正在寻找the all-pairs shortest paths problem。 SQL似乎不是解决此问题的正确工具 - 大量连接 - 因此我建议使用与MySQL接口的脚本语言。

Answer 2

在香草MySQL，没有简单的方法来做到这一点。

您可以安装OQGRAPH（这是专门用来存储图形插件存储引擎），它创建一个图形表，并发出这样的询问：

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

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