Условие задачи
С помощью алгоритма Дейкстры найдите путь минимального веса между вершинами s и t в нагруженном графе:
Ответ
Метод Дейкстры нахождения кратчайшего пути состоит в том, что вершинам графа присваиваются временные метки, а затем временные метки заменяются постоянными.
На первом шаге вершине, принятую за первую, присваивается постоянная метка L(x)=0 , а всем остальным временные метки .
На всех последующих итерациях: пусть вершина на предыдущей итерации получила постоянную метку. Из множества вершин, смежных ей и не имеющих постоянной метки, вычисляются новые метки по формуле:
Потяни
