Mike Mathcook's questions

Qual é a complexidade do código a seguir? É O(n^3log(n))?

#G is an undirected dense graph, which has N vertices.
import networkx as nx
def cal_minimax_path_matrix(G):
    MST = nx.minimum_spanning_tree(G)
    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

A complexidade de construir uma árvore_spanning_mínima é O(n^2). Qual é a complexidade de encontrar o caminho mais curto em uma árvore mínima_spanning? É O(nlog(n))?

O código é baseado no código de Madhav-99, veja:

https://github.com/Madhav-99/Minimax-Distance