所有对最短路径负重
All Pairs Shortest Path Under Weight
设 G 是给定的无向简单图，边权重为 w。是否存在时间复杂度为 O((n+m)log^*(n+m)) 的算法，该算法计算节点对 (u,v) 的数量，其中存在从 u 到 v 的路径且总权重低于一些给定常数W？寻找算法或证明不存在此类算法的证据。
我试过 union find + DFS 但它似乎不会只使用最多 n+m 调用 Find/Union...我也试过反证一个算法通过求解时间复杂度低于下限的 APSP，但无济于事。
成功显示不存在这样的算法：
通过矛盾假设存在这样的算法。
设G为给定的无向无权图，我们将计算图的直径如下：
- 为图中的每条边分配权重 1。因此，加权直径等于未加权直径。
- 我们发现图形的直径以m为界
- 使用算法执行二进制搜索以找到图形的直径（检查每个值是否计数 returns 为零）。
总的来说，我们在 O((n+m)log(n)log*(n+m)) 中找到 G 的直径。当前用于查找图形直径的最佳算法是 O(min(nm, ~n^2.4))。因此，至少，如果该算法成功，那么计算直径的时间复杂度将大大降低。不完全是证明，但足以满足我需要它的目的。
设 G 是给定的无向简单图，边权重为 w。是否存在时间复杂度为 O((n+m)log^*(n+m)) 的算法，该算法计算节点对 (u,v) 的数量，其中存在从 u 到 v 的路径且总权重低于一些给定常数W？寻找算法或证明不存在此类算法的证据。
我试过 union find + DFS 但它似乎不会只使用最多 n+m 调用 Find/Union...我也试过反证一个算法通过求解时间复杂度低于下限的 APSP，但无济于事。
成功显示不存在这样的算法：
通过矛盾假设存在这样的算法。
设G为给定的无向无权图，我们将计算图的直径如下：
- 为图中的每条边分配权重 1。因此，加权直径等于未加权直径。
- 我们发现图形的直径以m为界
- 使用算法执行二进制搜索以找到图形的直径（检查每个值是否计数 returns 为零）。
总的来说，我们在 O((n+m)log(n)log*(n+m)) 中找到 G 的直径。当前用于查找图形直径的最佳算法是 O(min(nm, ~n^2.4))。因此，至少，如果该算法成功，那么计算直径的时间复杂度将大大降低。不完全是证明，但足以满足我需要它的目的。