(train_graph, connected_component, max_distance)
return distance, matrix, cc
计算连通图中所有节点对的距离, 比Floyd算法快2.7倍左右
计算连通图中所有节点对的距离, 比Floyd算法快2.7倍左右
计算连通图中所有节点对的距离 比Floyd算法快2 . 7倍左右
def all_pair_Dijkstra(train_graph, connected_component, max_distance):
    '''
    计算连通图中所有节点对的距离, 比Floyd算法快2.7倍左右
    '''
    m = len(connected_component)
    cc = list(connected_component)
    distance = {}
    
    # 初始化距离矩阵
    matrix = [[0 for j in range(m)] for i in range(m)]
    
    for i in range(m):
        dist = Dijkstra(train_graph, connected_component, cc[i])
        for j,node in enumerate(cc):
            matrix[i][j] = dist[node]
            # 保存我们想要的距离
            if matrix[i][j] > 1 and matrix[i][j] <= max_distance \
                          and (cc[i], cc[j]) not in distance.keys() \
                          and (cc[j], cc[i]) not in distance.keys():
                distance[(cc[i], cc[j])] = matrix[i][j]
                    
    return distance, matrix, cc
def all_pair_Dijkstra ( train_graph , connected_component , max_distance ) : m = len ( connected_component ) cc = list ( connected_component ) distance = { } # 初始化距离矩阵 matrix = [ [ 0 for j in range ( m ) ] for i in range ( m ) ] for i in range ( m ) : dist = Dijkstra ( train_graph , connected_component , cc [ i ] ) for j , node in enumerate ( cc ) : matrix [ i ] [ j ] = dist [ node ] # 保存我们想要的距离 if matrix [ i ] [ j ] > 1 and matrix [ i ] [ j ] <= max_distance and ( cc [ i ] , cc [ j ] ) not in distance . keys ( ) and ( cc [ j ] , cc [ i ] ) not in distance . keys ( ) : distance [ ( cc [ i ] , cc [ j ] ) ] = matrix [ i ] [ j ] return distance , matrix , cc