Изменения
Нет описания правки
# Предложите алгоритм поиска всех ребер, которые лежат хотя бы в одном MST за $O(E \log{V})$.
# Предложите алгоритм поиска всех ребер, которые лежат во всех MST за $O(E \log{V})$.
#Модифицируем алгоритм Дейкстры следующим образом: будем вместо приоритетной очереди использовать FIFO-очередь. Если при релаксации до вершины, которая уже была в очереди, расстояние улучшается, добавим ее снова в очередь. Докажите, что полученный алгоритм ищет кратчайшие пути в графе с отрицательными ребрами, но без отрицательных циклов, за $O(VE)$.
</wikitex>
