加权图中的最短路径 [英] Shortest path in a weighted map
问题描述
如果我有如下所示的MySQL邻接表:
节点,相邻节点,距离
A,B,30
B,C,100
C,A,50
C,D,20
D,A,5
D,B,5
找到节点之间最短距离的最佳方法是什么?例如,走A-> B是最快的A-> D-> B,总距离为10.但是,我的实际数据大约有10,000个节点(但只有几个连接路径).
(如果需要,我很高兴将数据转换为更合理的格式.)
If I have a MySQL adjacency list as follows:
node,adjacantnode,distance
A,B,30
B,C,100
C,A,50
C,D,20
D,A,5
D,B,5
What is the best approach to take to find the shortest distance between nodes? For example, to go A->B is quickest A->D->B totalling a distance of 10. My actual data, however, has around 10,000 nodes (but only a few connecting paths).
(I''m obviously quite happy to transform my data to a more sensible format if needs be.)
Thanks in advance!
推荐答案
^ ]
正如Ed Nutting所说,这是知名情况仍在等待
完整"的答案.
但是,如果最大路径数量有限且已知,则可以使用快速且肮脏的解决方案.定义表的次数取决于您的连接次数,然后计算路径距离.例如类似(pseudo):
As Ed Nutting posted this is a well-known situation still waiting for the
''complete'' answer.
However, if you have a limited and known amount of maximum paths then you could possibly use a quick and dirty solution. Define the table as many times as you have connections and then calculate the path distance. For example something like (pseudo):
select a1.distance + a2.distance + a3.distance + a4.distance ...
from tablename a1
left outer join tablename a2 on a1.node = a2.adjacentnode
left outer join tablename a3 on a2.node = a3.adjacentnode
left outer join tablename a4 on a3.node = a4.adjacentnode...
明显的缺点是您必须知道最大路径的长度.但是正如您提到的,这很小.
另一个变体是使用递归公用表表达式(CTE)创建递归查询.有关更多信息,请参见:递归CTE [ ^ ]
哦,顺便说一句,我根本不知道是否应该发布此内容,请参见哦,加拿大 [^ ]:)
The obvious downside is that you have to know the length of the maximum path. But as you mentioned this is small.
Another variation would be to create a recursive query using recursive Common Table Expressions (CTE). For more information, see: Recursive CTEs[^]
Oh, by the way I don''t know if I should have posted this at all, see Oh Canada[^] :)
这篇关于加权图中的最短路径的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!