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

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

Читайте также:
  1. I Психологические принципы, задачи и функции социальной работы
  2. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  3. I. ЗАДАЧИ ПЕДАГОГИЧЕСКОЙ ПРАКТИКИ
  4. I. Решение логических задач средствами алгебры логики
  5. I. Розв’язати задачі
  6. I. Ситуационные задачи и тестовые задания.
  7. II. Основные задачи и функции
  8. II. Основные задачи и функции
  9. II. Решение логических задач табличным способом
  10. II. ЦЕЛИ, ЗАДАЧИ И ПРИНЦИПЫ ДЕЯТЕЛЬНОСТИ ВОИ
  11. II. Цель и задачи государственной политики в области развития инновационной системы
  12. III. Решение логических задач с помощью рассуждений

Присвоим каждой дуге имя. Приставим себе, что эта сеть состоит из труд, по которым течет вода и известна пропускная способность этих труб.

1.Рассмотрим путь (a->b) соединяющий точку S и T. По этому пути в T попадает две единицы продукции, при этом труба b будет насыщена. Вычитает из показателей труб число 2, тогда получим следующую сеть.

2. Далее видно, что по дуге (k,f) в T попадает –1 единица продукции и по пути (c,p,f) попадает –2 единицы продукции, по пути (a,m,f) –1 единица продукции. Вычитая соответствующие значения получаем следующий граф. Если рассмотреть последнюю сеть, то видно, что насыщены трубы b и f – и это означает, что в точку T попадает 2+4=6 единиц продукции, т.е. пропускная способность этой сети или максимальный поток из S и T =6.

Если рассмотреть простой разрез (b;f), то суммарная пропускная способность этих дуг =6, и равна максимальной величине потока из S и Т.По теореме Форда-Фанкерсона максимальная величина потока через сеть равна минимальному из всех пропускных способностей её простых разрезов. Значит минимальный разрез нашей сети состоит из дуг b и f.

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

Алгоритм Дейкстры для нахождения кратчайших путей в графе Разработан для нахождения кратчайшего пути между заданным исходным узлом и любым другим узлом сети. В процессе перехода от узла i к узлу j используется процедура пометки рёбер. Обозначим ui кратчайшее расстояние, от исходного узла до узла i, через dij – длинной ребра (i,j). Тогда для узла j определим метку [uj;i]=[ui+dij,i]; dij>=0. Метки в алгоритме Дейкстры могут быть двух типов: временными и постоянными. Временные метки могут изменяться, если будет найден более короткий путь к данному узлу. Когда станет очевидно, что не существу ет более короткого пути от исходного узла к данному, статус временной метки изменится на постоянную.

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

Шаг 0. Исходному узлу присваивается метка [0:-]:i=1;

Шаг i. а) вычисляются временные метка [ui+dij;i} для всех узлов j которых можно достич непосредственно из узла I и которые не имеют постоянных меток, если узел j узел имеет метку [uj;k] полученный от другого узла k и если выполняется условие ui+dij<uj, то метки [uj;k] заменяется на метку [ui+dij;i].

б)если все узлы имеют постоянные метки процесс вычисления заканчивается. В противном случае выбирается метка: [ur;S] с наименьшим значение расстояния ui среди всех временных меток,если несколько-произволен


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

Поиск по сайту:



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