Дан неориентированный взвешенный граф с n вершинами и m ребрами. Как мне построить алгоритм, который занимает не более O ((n + m) log (n + m)) для поиска вершины, для которой минимальное расстояние кратчайшего пути до набора вершин S \ в V равно максимизировано?
Я знаю, что могу l oop пройти через все вершины и с помощью алгоритма Дейкстры найти кратчайший путь к каждой из вершин в S, но это, несомненно, займет гораздо больше, чем O ((n + m) log (п + т)).