加权下的所有对最短路径

Question

设G是一个给定的无向简单图，边权为w，存在一个具有时间复杂度O((n+m)log^*(n+m))的算法，在给定的常数W下，有一个节点对(u，v)存在一个由u到v的路径.寻找算法或证明不存在这样的算法。

我尝试过union find + DFS，但是似乎不会只使用n+m调用来查找/联合.我还尝试了dis-通过求解时间复杂度低于下限的APSP来证明算法的存在，但没有结果。

Answer 1

成功地表明不存在这样的算法：

假设存在这样一种算法。

设G是一个给定的无向非加权图，我们将计算出图的直径如下：

1. 给图上的每个边分配权重1。因此，加权直径等于未加权直径。
2. 我们发现图的直径是由m
3. 限定的，用该算法进行二值搜索以求图的直径(检查每个值是否计数为零)。

总之，我们在O((n+m)log(n)log*(n+m))中找到了G的直径。目前求图直径的最佳算法是O(min(nm，~n^2.4))。因此，如果该算法成功的话，计算直径的时间复杂度就会大大降低。不完全是证据，但足以达到我所需要的目的。