Расстояние между узлами во Флойд Уоршолл

Question

Эта страница википедии объясняет алгоритм Флойда Варшалла, чтобы найти кратчайший путь между узлами в графе. Страница википедии использует график слева от изображения как начальный график (до первой итерации, когда k = 0), а затем показывает оставшиеся итерации (k = 1 и т. д.), но он не объясняет значимость чисел между узлами и то, как эти числа вычисляются. Например, на начальном графике, когда k = 0, почему на ребре от 1 до 3 стоит -2, а на ребре от 2 до 3 - 3, как рассчитываются?

Кроме того, когда k = 2, на странице википедии написано:

Путь [4,2,3] не рассматривается, поскольку [2,1,3] - кратчайший путь, встречающийся до сих пор от 2 до 3.

Почему [2,1,3] короче [4,2,3]?

Answer 1

Числа на краях - просто веса. Это часть ввода. Алгоритм не вычисляет их.

[2, 1, 3] не короче, чем [4, 2, 3]. Это короче, чем [2, 3], хотя. Это единственное, что имеет значение.