找到边的权重为1的所有对的距离的最佳算法

Question

正如标题所说,我正在尝试实现一种算法,该算法找出给定图形中所有节点对之间的距离.但还有更多:(可能有助于你的事情)

• 图表未加权.这意味着可以将所有边缘视为权重为1.
• |E| <= 4*|V|
• 图表非常大(最多144个深度)
• 该图是针对性的
• 可能有周期
• 我正在用python编写我的代码(如果你引用算法,那么代码也会很好:))

对于所有对,我都知道约翰逊的算法,Floyd-Warshal和Dijkstra.但是当图表具有权重时,这些算法是好的.

我想知道我的情况是否有更好的算法,因为这些算法用于加权图.

谢谢!

Answer 1

还有待改进的空间,因为在未加权的图形中,您获得的附加属性不适用于加权图形,即:

对于直接连接A到C的任何边缘,您确定通过第三个节点B没有更短的路径.

考虑到这一点,您应该能够简化Dijkstra的算法:您可能知道,它适用于三组节点:

1. 已确定最短路径的那些,
2. 计算了初步距离的那些和
3. 那些尚未探索过的.

当跟随e从A(1.)到C(3.)的边缘时,原始Dijkstra将节点C从(3.)移动到(2.).由于上述属性在所有图形中都有,因此您可以将其直接添加到集合(1.)中,这样更有效.

以下是基本观察:上面概述的过程基本上是BFS(广度优先搜索),即您可以找到从某个固定节点v到任何其他节点的距离O(|V| + |E|).

您在原始问题中没有提到图形基本上是一个带有一些洞的网格.这是一个更强大的要求,我相信你可以利用它.这样做的"网格图最短路径"快速搜索产生本文并承诺O(sqrt(n))在最好的情况下.由于你指定的问题结构相当合理,我几乎可以肯定还有几篇你可能想要研究的论文.

Answer 2

从每个节点运行广度优先搜索.总时间:O(| V | | E |)= O(| V | ²),这是最佳的.