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

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

Читайте также:
  1. а) Начертить кинематическую схему __________________________________________________________________
  2. Блок-схему
  3. В. Рассмотрите схему и выполните задания B8–B11.
  4. Вероятность её нахождения вдоль оси x(б)
  5. Взятие отделяемого дыхательных путей
  6. ВОПРОС N 47. Поиск и согласование наиболее эффективных путей и средств реализации принятой
  7. Воспалительные заболевания верхних отделов половых путей (органов малого таза)
  8. Воспалительные заболевания нижних отделов половых путей
  9. Временной ряд для нахождения личных целей
  10. Габариты путей эвакуации
  11. Глава 6 РАСХОЖДЕНИЕ ПУТЕЙ
  12. Глава 8. Понятие алгоритма

Шаг 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 сек.)