Минимальное время для уведомления всех узлов сети

Question

Проблема: ввод представляет собой неориентированный граф с весами на ребрах, который представляет сеть компьютеров, где веса ребер означают минимальное время, необходимое для отправки сообщения между двумя компьютерами.Мы выбираем одну вершину этого графа и отправляем сообщение в связанные вершины.Когда вершина получает сообщение, она отправляет его соседям только один раз.Необходимо найти минимальное время для уведомления каждой вершины в графе.

Я реализовал алгоритм грубой силы, чтобы исключить это, но он слишком медленный (N ^ 2).Сначала я подумал, что это можно решить как вес минимального остовного дерева, но ему нужно что-то сверх него.

Я думаю, что существует некоторый алгоритм для этой проблемы ...

Answer 1

Модификация алгоритма dijkstras должна подойти для этой цели.Но вместо поиска кратчайшего пути к конкретному узлу алгоритм завершается, как только все узлы были посещены.После выполнения вышеизложенного проблема сводится к извлечению узла с максимальным расстоянием от узла-источника из таблицы, построенной во время обхода графа.

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|)худший случай.