设G为给定的无向简单图，边权为w，是否存在一种时间复杂度为O((n+m)log^*(n+m))的算法，计算在某给定常数w下存在从u到v的总权路径的节点对(u,v)的个数?寻找一个算法或证明不存在这样的算法。
我已经尝试过联合查找+ DFS，但似乎只会使用n+m调用查找/联合…我也曾试图通过求解时间复杂度低于下界的APSP来否定一种算法的存在性，但没有成功。
成功显示不存在这样的算法:
通过矛盾假设存在这样一个算法。
设G是一个给定的无向无权图，我们将计算图的直径如下:
- 给图上的每条边赋权值1。因此，加权直径等于未加权直径。 我们发现图的直径以m为界。
- 使用算法执行二分搜索以查找图的直径(检查每个值计数是否返回零)。
总的来说，我们发现G的直径为O((n+m)log(n)log*(n+m))。目前寻找图直径的最佳算法是O(min(nm， ~n^2.4))。因此，至少，如果该算法成功，那么计算直径的时间复杂度将大大降低。不完全是一个证明，但对于我需要它的目的来说已经足够好了。