加权图中的最短路径 [英] 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屋！