Алгоритм Флойда — различия между версиями
Материал из ALL
(Новая страница: «'''Алгоритм Флойда''' — это алгоритм нахождения минимальных расстояний между пунктами. ==…») |
|||
Строка 24: | Строка 24: | ||
'''{m<sub>12</sub>, m<sub>13</sub>, ..., m<sub>n n-1</sub>}'''. | '''{m<sub>12</sub>, m<sub>13</sub>, ..., m<sub>n n-1</sub>}'''. | ||
== Другие алгоритмы: == | == Другие алгоритмы: == | ||
− | *[[ | + | *[[алгоритм Дейкстры]]; |
− | *[[ | + | *[[алгоритм Джонсона]]; |
− | *[[ | + | *[[алгоритм Флойда]]; |
+ | *[[алгоритм Ху]]. | ||
== Ссылки == | == Ссылки == | ||
* [[Участник:Logic-samara]] | * [[Участник:Logic-samara]] | ||
[[Категория:Логистика]][[Категория:Алгоритмы]] | [[Категория:Логистика]][[Категория:Алгоритмы]] |
Версия 17:29, 1 февраля 2016
Алгоритм Флойда — это алгоритм нахождения минимальных расстояний между пунктами.
Содержание
Обозначения
Введём обозначения.
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}.
Другие алгоритмы:
- алгоритм Дейкстры;
- алгоритм Джонсона;
- алгоритм Флойда;
- алгоритм Ху.