寻找边权为1的所有点对距离的最佳算法
正如标题所说，我正在尝试实现一个算法，用来找出给定图中所有节点之间的距离。不过还有更多信息：（这些可能对你有帮助）
- 这个图是无权重的。也就是说，所有的边都可以看作是权重为1。
|E| <= 4*|V|- 这个图相当大（最多大约有144层深度）
- 这个图是有向的
- 可能会有循环
- 我用python写代码（如果你提到算法，能给点代码示例就更好了 :))
我知道有约翰逊算法、弗洛伊德-沃尔沙尔算法和迪杰斯特拉算法可以用来处理所有节点对之间的距离。但这些算法适合有权重的图。
我在想，是否有更适合我这种情况的算法，因为这些算法是为有权重的图设计的。
谢谢！
10 个回答
我不知道如果所有边都没有权重，你怎么测量距离，但你可以看看Edmond的Blossom V算法。你可以参考这个链接：http://code.activestate.com/recipes/221251-maximum-cardinality-matching-in-general-graphs。这里还有一些类似的内容：http://wilanw.blogspot.com/2009/09/maximumminimum-weighted-bipartite.html。
从每个节点开始进行广度优先搜索。总的时间复杂度是 O(|V| |E|) = O(|V|2)，这是最优的。
在无权图中，有改进的空间，因为你可以获得一个额外的属性，而这个属性在有权图中是不存在的，具体来说：
对于任何直接连接A和C的边，你可以确定通过第三个节点B没有更短的路径。
考虑到这一点，你应该能够简化Dijkstra算法：你可能知道，它是通过三组节点来工作的：
- 已知最短路径的节点，
- 已经计算出初步距离的节点，
- 尚未探索的节点。
当你从节点A（1.）沿着边e移动到节点C（3.）时，原始的Dijkstra算法会把节点C从（3.）移动到（2.）。但是，由于上述属性在你所有的图中都成立，你可以直接把它加入到集合（1.）中，这样效率更高。
这里有一个重要的观察：上面描述的过程基本上就是广度优先搜索（BFS），也就是说，你可以在O(|V| + |E|)的时间内找到某个固定节点v到任何其他节点的距离。
你在最初的问题中没有提到这个图基本上是一个有一些空洞的网格。这是一个更强的要求，我相信你可以利用这一点。快速搜索“网格图最短路径”会得到这篇论文，它承诺在最佳情况下可以达到O(sqrt(n))。由于你指定的问题结构相当明确，我几乎可以肯定还有几篇论文你可能想要查看。