Вопрос: рассмотрим ориентированный граф с 5 вершинами. Пусть алгоритм Дейкстры дает кратчайшие пути от узла s ко всем остальным узлам, как показано на рис. 1. Пусть вес ребра (x, t) увеличивается и предполагается, что все узлы каким-то образом получают эту информацию. Как node s модифицирует алгоритм Дейкстры, чтобы сделать минимальные повторные вычисления? Предоставьте окончательное решение в виде «Узел s запускает алгоритм Дейкстры, инициализируя S как и сохраняя список (‹ каждый узел >) как».
Мой вопрос... Разве это не вопрос с подвохом, потому что все, что он сделает, это увеличит кратчайший путь от s до t, верно?
ладно моя картинка не работает
но это работает примерно так:
s->y->x->t
y также указывает на z. у-> г
это однонаправленные стрелки.
