是否有比 O(n2) 更快的算法来计算加权非循环图中每对之间的成本仅，假设我不需要最短路径，而只需要我想要的路径如果使用简单的 BFS 得到？我不需要实际路径，只需要路径成本。我目前的解决方案只是从每个节点开始做一个 BFS，同时跟踪沿途的边的权重，但这显然是 O(n2)，我想知道是否有可能做得更好。
最佳答案
不，没有比 O(n2) 更好的算法了。
该算法将需要至少遍历每一对。图中有 O(n2) 可能的对:
.因此算法底部边界是
= O(n2).
关于algorithm - 仅计算加权图中所有对之间路径的成本，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29021473/