对于无向、未加权的图，计算其平均最短路径长度的算法的时间复杂度与计算图直径的算法的复杂度(即最长最短路径之间的最长最短路径)是否存在差异？两个顶点？
最佳答案
根据 Wikipedia , 要计算图形的直径，您应该首先找到所有对的最短路径。在计算出所有对最短路径后，两种算法都减少到 O(V^2) 计算，因此它们的复杂度相同。
关于algorithm - 图的平均最短路径长度和直径算法的时间复杂度是否存在差异？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6911927/