问询给定代码的时间复杂度及MST中最短路径的复杂度

代码实现 #

# G is an undirected dense graph, which has N vertices.
import networkx as nx
import numpy as np

def cal_minimax_path_matrix(G):
    MST = nx.minimum_spanning_tree(G)
    N = G.number_of_nodes()
    minimax_matrix = np.zeros((N, N))

    for i in range(N):
        for j in range(N):
            if j > i:
                max_weight = -1 
                path = nx.shortest_path(MST, source=i, target=j)
                for k in range(len(path)-1):
                    if MST.edges[path[k], path[k+1]]['weight'] > max_weight:
                        max_weight = MST.edges[path[k], path[k+1]]['weight']
                minimax_matrix[i,j] = minimax_matrix[j,i] = max_weight
                
    return minimax_matrix

问题解答 #

1. 该代码的时间复杂度是否为O(n³log(n))？ #

不是。具体分析：

• 构建MST的复杂度为给定的O(n²)，属于低阶项可忽略。
• 外层两层循环仅在j > i时执行逻辑，总迭代次数为O(n²)。
• 每次迭代中：
  • MST是树结构，NetworkX用广度优先搜索(BFS)查找两点路径，时间复杂度为O(n)（树有n个顶点、n-1条边，BFS遍历所有节点最多O(n)）。
  • 遍历路径求最大权重：树中两点路径最长包含n-1条边，这一步复杂度为O(n)。
• 单次迭代总复杂度为O(n)，两层循环总复杂度为O(n²) * O(n) = O(n³)，加上MST的O(n²)，最终整体时间复杂度为O(n³)，而非O(n³logn)。

2. 在minimum spanning tree（MST）中查找最短路径的复杂度是否为O(nlog(n))？ #

不是。MST是树结构，任意两点间路径唯一，这条路径就是边数最少的最短路径（无权重场景）。NetworkX中nx.shortest_path在无权重树中采用BFS实现，时间复杂度为O(n)。即使考虑带权重的最短路径，树中也无需复杂算法，直接遍历路径即可，复杂度仍为O(n)，不存在O(nlogn)的情况。

内容的提问来源于stack exchange，提问作者Mike Mathcook