Каким образом увеличение веса края на графике влияет на алгоритм Дейкстры?

Question

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

Мой вопрос ... Разве это не вопрос с подвохом, потому что все это будет делать, это увеличить кратчайший путь от s до t правильно?

хорошо так что моя картина разве работает

но это что-то вроде это работает:

s-> y-> x-> т

у также указывает на г. y-> z

это стрелки направления в одну сторону.

Answer 1

Если (s, y), (y, z), (y, x), (x, t) - единственные ребра в этом графе, то да: это только увеличивает вес (или расстояние) кратчайший путь от s до t, так как существует только один такой путь.