首页 > 数据库 > mysql解决Dijkstra问题

mysql解决Dijkstra问题

2014年4月28日 1,212 人浏览 发表评论 阅读评论

看到有人说这个问题,尝试着解决一下。测试图:
Dijkstra

-- mysql 解决 Dijkstra
-- 创建节点表
CREATE TABLE if not exists `Dijkstra_Node`  (
	`A` CHAR(1) NULL DEFAULT NULL,
	`B` CHAR(1) NULL DEFAULT NULL,
	`val` TINYINT(4) NULL DEFAULT NULL
);
-- 清空
truncate table Dijkstra_Node;
-- 插入测试数据

insert into Dijkstra_Node(A,B,val) values
('A','B',6),
('A','C',3),
('B','C',2),
('C','D',3),
('B','D',5),
('D','F',3),
('D','E',2),
('E','F',5),
('C','E',4);

-- 结果表
CREATE TABLE if not exists `Dijkstra_Result` (
	`target` CHAR(1) NULL DEFAULT NULL,
	`val` SMALLINT(6) NULL DEFAULT NULL
);
-- 清空结果表
truncate table Dijkstra_Result;
-- 开始节点 A
set @start='A';
-- 初始 到自己距离0
insert into Dijkstra_Result values(@start,0);

解决的sql只有一句,如下,是一句哦,不过要执行n-1次,n是节点数,每次插入一个找到的。

insert into Dijkstra_Result(target,val)
select B,(select val from Dijkstra_Result where target=t.A)+val as val from (
select * from (
select A,B,val from Dijkstra_Node where A in (select target from Dijkstra_Result)
and B not in (select target from Dijkstra_Result )
union
select B,A,val from Dijkstra_Node where B in (select target from Dijkstra_Result )
and A not in (select target from Dijkstra_Result )
) as t ) as t order by val asc limit 1;

结果:

select * from Dijkstra_Result;
A 0
C 3
B 5
D 6
E 7
F 9

分类: 数据库 标签: ,
1 Star2 Stars3 Stars4 Stars5 Stars 来给这篇文章评分吧!
Loading ... Loading ...
  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.