для которых еще
для которых еще не вычислена оценка расстояние и, это главное, минимальное значение в D по множеству вершин, принадлежащих T, считается окончательной оценкой для вершины, на которой достигается этот минимум. С точки зрения здравого смысла этот факт достаточно очевиден. Другой “заход” в эту вершину возможен по пути, содержащему большее количество дуг, а так как веса неотрицательны, то и оценка пути будет больше. В книгах [11], [12] можно найти доказательство этого факта.
Пример
Его матрица смежности:
? 3 7 ? ? ?
1 ? 2 ? ? 1
A= ? 1 ? 4 4 ?
? ? ? ? 1 5
? ? 1 ? ? 3
? ? ? 2 ? ?
В таблице приведена последовательность шагов (итераций) работы алгоритма. На первом шаге минимальное значение D достигается на второй вершине. Она исключается из множества T, и улучшение оценки до оставшихся вершин (3,4,5,6) ищется не по всем вершинам, а только от второй.
№ итерации D[1] D[2] D[3] D[4] D[5] D[6] T
1 0 3 7 ? ? ? [2,3,4,5,6]
2 0 3 5 ? 11 4 [3,4,5,6]
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
