Алгоритм Флойда
Материал из ALL
Версия от 11:32, 29 декабря 2017; Logic-samara (обсуждение | вклад)
Алгоритм Флойда — это алгоритм нахождения минимальных расстояний между пунктами.
Содержание
Обозначения
Введём обозначения.
n - число пунктов.
dij - расстояние от пункта i до пункта j, зависящее от направления.
Алгоритм нахождения минимальных расстояний
Входные данные: n; {d12, d13, ..., dn n-1}.
Выходные данные: {d12, d13, ..., dn n-1}.
Введём дополнительные обозначения.
mij - маршрут от пункта i до пункта j.
Алгоритм получения оптимальных маршрутов
Входные данные: n; {d12, d13, ..., dn n-1}.
Выходные данные: {d12, d13, ..., dn n-1}; {m12, m13, ..., mn n-1}.
Другие алгоритмы:
- алгоритм Дейкстры;
- алгоритм Флойда;
- алгоритм Ху;
- алгоритм Джонсона.