Рассмотрим ориентированный граф, показанный на рисунке ниже. Существует несколько кратчайших путей между вершинами S и T. Какой из них будет сообщен алгоритмом кратчайшего пути Дейстры? Предположим, что на любой итерации кратчайший путь к вершине v обновляется только тогда, когда обнаруживается строго более короткий путь к v. 
Мой ответ - SBDT, но в решениях он дает SACET, я не могу понять, почему.
Алгоритм Дейкстры выбирает узлы следующим образом:
B(3) from S
A(4) from S
C(5) from A
E(6) from C
D(7) from S or B
G(8) from E
T(10) from D or E
Таким образом, кратчайший путь к T — это SBDT, SDT или SACET.
Но из-за "the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered" при посещении E предшествующий узел T для кратчайшего пути будет установлен как E и больше не изменится.
Таким образом, ответ SACET.
Запустите его в http://dracos.co.uk/maths/dijkstra/. Ответ: SDT. . Причина: После узла S рассматриваются его непосредственные соседи, т.е.: A(4),D(7),B(3) Теперь рассматриваются непосредственные соседи этих узлов. Мы приходим к SDT(10) до того, как рассматривается узел C, потому что C не является непосредственным соседом S. Ответ: SDT
