АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Изложить алгоритм Флойда для нахождения кратчайших путей в графе и перечислить аспекты применения алгоритма

Читайте также:
  1. I. Основы применения программы Excel
  2. II. Психологические аспекты делового общения
  3. SALVATOR - это переход физического явления в семантико-нейронный алгоритм (инструкцию) освобождения человека от негативных последствий этого явления.
  4. V2: Применения уравнения Шредингера
  5. XII. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
  6. АКТУАЛЬНЫЕ АСПЕКТЫ ПАТОГЕНЕЗА ВОСПАЛЕНИЯ. СОВРЕМЕННОЕ ПРЕДСТАВЛЕНИЕ О ПАТОГЕНЕЗЕ СЕПСИСА И СИНДРОМА СИСТЕМНОГО ВОСПАЛИТЕЛЬНОГО ОТВЕТА
  7. Акты применения права
  8. Акты применения права
  9. Акты применения права, их особенности и виды
  10. Акты применения права, их характерные черты, реквизиты, виды.
  11. Акты применения права: понятие, особенности и виды.
  12. Акты применения права: понятие, признаки, виды

Шаг 0. Определяем начальную матрицу расстояний D0 и матрицу последовательности узлов S0. диагональные элементы обеих матриц помечаются знаком «-», так как эти элементы в вычислениях не участвуют. Полагаем k =1птак как эти элементы в вычислениях не участвуют. Основной шаг k:

Задаем строку k и столбец k как ведущую строку и ведущий столбец. Рассматриваем возможность применения треугольного оператора ко всем элементам dij матрицы Dk-1. если выполняется неравенство ,то выполняются следующие действия:а) создаем матрицу Dk путем замены в матрице Dk-1 элемента dij на сумму ;

б) создаем матрицу Sk путем замены элемента sj на k.

1)После реализации n шагов алгоритма можно определить кратчайший путь по матрицам Dn и Sn между узлами i и j, пользуясь следующими правилами: Расстояние между i и j равно dij в матрице Dn.2)Промежуточные узлы пути от узла i к узлу j определяем по матрице Sn.

Пусть sij = k, тогда имеем путь i → j → k.

Если далее sik = k и skj = k, тогда считаем, что весь путь определен, так как найдены все промежуточные узлы. В противном случае повторяем описанную процедуру для путей от узла i к узлу j и от узла k к узлу j.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |


Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)