Найти путь между узлами с помощью 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

В ванили MySQL нет простого способа сделать это.

Вы можете установить OQGRAPH (это механизм хранения плагинов, предназначенный для хранения графиков), создать в нем таблицу графиков и выполнить запрос, подобный следующему:

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

, который будет использовать алгоритм Дейкстры, чтобы найти кратчайший путь между 1 и 3.

Answer 2

Я полагаю, что вы ищете проблему кратчайших путей для всех пар . Похоже, что SQL не является подходящим инструментом для решения этой проблемы - множество соединений - поэтому я предлагаю использовать язык сценариев, который взаимодействует с MySQL.