仅计算加权图中所有对之间路径的成本
Compute costs only of paths between all pairs in weighted graph
是否有比 O(n2) 更快的算法来计算加权非循环图中每对之间的成本仅，假设我不需要最短路径但只是如果使用简单的 BFS 我会得到的路径？我不需要实际路径，只需要路径成本。我目前的解决方案只是从每个节点开始做一个 BFS，同时跟踪沿途的边的权重，但这显然是 O(n2)，我想知道是否有可能做得更好。
不，没有比O(n2)更好的算法了。
该算法将需要至少遍历每一对。图中有 O(n2) 个可能的对：
。因此算法底部边界是 = O(n2).
是否有比 O(n2) 更快的算法来计算加权非循环图中每对之间的成本仅，假设我不需要最短路径但只是如果使用简单的 BFS 我会得到的路径？我不需要实际路径，只需要路径成本。我目前的解决方案只是从每个节点开始做一个 BFS，同时跟踪沿途的边的权重，但这显然是 O(n2)，我想知道是否有可能做得更好。
不，没有比O(n2)更好的算法了。
该算法将需要至少遍历每一对。图中有 O(n2) 个可能的对：