Изменения

Выберем из всех путей между данными вершинами путь наименьшей длины. Пусть он не простой; тогда в нём содержатся две одинаковые вершины <math>V_i</math> и <math>V_j</math>, <math>i < j</math>. Удалим из исходного пути отрезок от <math>E_{i+1}</math> до <math>V_j</math>, включительно. Конечная последовательность также будет путём между <math>V_i</math> и <math>V_j</math> и станет короче исходной. Значит, исходный путь не был кратчайшим; предположение неверно, выбранный путь – простой.