查找節點之間的路徑與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之間。