algorithm - 通知网络所有节点的最短时间

Question

问题:输入是无向图，边上有权重，表示计算机网络，其中边的权重表示在两台计算机之间发送消息所需的最短时间。我们选择该图的一个顶点并向连接的顶点发送一条消息。当顶点收到消息时，它只会将它重新发送给邻居一次。需要找到通知图中每个顶点的最短时间。

我已经实现了蛮力算法来解决这个问题，但它太慢了 (N^2)。首先我认为这可以作为最小生成树的权重来解决，但它需要一些东西。

我认为这个问题有一些现有的算法......

Answer 1

对 dijkstras algorithm 的修改应该为此目的而做。但是，该算法不是搜索到特定节点的最短路径，而是在访问了所有节点后终止。完成上述操作后，问题就简化为从遍历图时建立的表中提取与源节点距离最大的节点。

longest_path(node):
    # dijkstras algo
    path_len = map()
    queue = priority_queue()  # priority-queue sorted by distance to source-node
    visited = set() 

    path_len[node] = 0
    queue.put(node)       

    while queue not empty
        n = queue.pop()

        if n in visited
            continue

        for neighbor in n.neighbors()
            dist = path_len[n] + n.edge_length(neighbor)
            if neighbor not in path_len or path_len[neighbor] > dist
                queue.offer(neighbor)
                path_len[neighbor] = dist

         visited.add(n)

     # find the node with the maximum distance to the source-node
     max = -1
     res = NULL
     for n in path_len.keys()
         if path_len[n] > max
             max = path_len[n]
             res = n

     return res

上述算法在O(|E| + |V| log |V|) 最坏情况下有效。