расстояние между узлами в floyd warshall

Этастраница в Википедии объясняет алгоритм Флойда Уоршалла для поиска кратчайшего пути между узлы в графе. На странице википедии используется график слева от изображения использует график слева от изображения в качестве начального графика (до первой итерации, когда 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]?


person Leahcim    schedule 11.12.2016    source источник


Ответы (1)


Цифры по краям — это просто веса. Это часть ввода. Алгоритм их не вычисляет.

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

person kraskevich    schedule 11.12.2016
comment
хорошо, почему [2,1,3] короче [2,3]? потому что 2->1 (вес 4) и 1 -> 3 (вес -2) равно 2 (общий вес), а [2,3], что равно 3? - person Leahcim; 11.12.2016
comment
@Leahcim Да. Длина пути равна сумме весов его ребер. - person kraskevich; 11.12.2016