Find path between nodes with SQL
i have two mysql tables: nodes and relations
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
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 |
+---------+-----------+------+---------+
In vanilla MySQL
, there is no easy way to do it.
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:
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
.
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.
精彩评论