Safari - Примечание. Попытка получить свойство необъекта & hellip; post-template.php в строке 656

Правильность алгоритма Дейкстры:

У нас есть два набора вершин на любом шаге алгоритма. Набор А состоит из вершин, на которые мы вычислили кратчайшие пути. Множество B состоит из оставшихся вершин.

Индуктивная гипотеза: на каждом шаге мы будем считать, что все предыдущие итерации верны.

Индуктивный шаг: когда мы добавляем вершину V в множество A и задайте расстояние до dist [V], мы должны доказать, что это расстояние оптимально. Если это не оптимально, то должен существовать некоторый другой путь к вершине V, которая имеет более короткую длину.

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

Теперь, поскольку dist [V] & lt; = dist [X], поэтому любой другой путь к V будет иметь длину по крайней мере dist [V], если граф не имеет отрицательных длин ребер.

Таким образом, для работы алгоритма dijkstra веса ребер должны быть не отрицательными.