Как применить алгоритм Дейкстры?

Question

[The_XXI]

Подскажите, как найти кратчайший путь из s в t, точнее как объяснить, что он кратчайший с помощью алгоритма Дейкстры?

Comments

[poniyur]

вам алгоритм пересказать или что?

[jcmvbkbc]

как объяснить, что он кратчайший с помощью алгоритма Дейкстры?

По определению алгоритма Дейкстры же -- если алгоритм находит кратчайшие пути от одной из вершин в графе ко всем остальным, то путь найденный алгоритмом от одной вершины до другой -- кратчайший по определению.

[The_XXI]

poniyur, уже разобрался по ссылке ниже

Answer 1

[Руслан .]

Вот тут есть доказательство корректности алгоритма Дейкстры.
Там же описано почему путь кратчайший.
https://neerc.ifmo.ru/wiki/index.php?title=%D0%90%...