|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Методические указания. Рассмотрим методику поиска кратчайшего пути на примереРассмотрим методику поиска кратчайшего пути на примере. Пусть имеется орграф, представленный на рисунке 1.
Рис. 1. Исходные данные к задаче в виде взвешенного орграфа
Приведенный граф может быть записан также в виде таблицы:
Пусть необходимо найти кратчайший путь между вершинами 1 и 4. Введем обозначение: С(Т) – длина кратчайшего пути из вершины 1 в вершину Т. Оставленная задача состоит в вычислении С(4) и указании пути с минимальной стоимостью проезда. Рассмотрим подробнее взвешенный орграф, представленный на рисунке 1. В вершину 4 можно попасть либо из вершины 2, пройдя путь, равный 4,либо из вершины 5, пройдя путь, равный 5. Поэтому справедливо соотношение Таким образом, проведена реструктуризация (упрощение) задачи – нахождение С(4) сведено к нахождению С(2) и С(5). В вершину 5 можно попасть либо из вершины 3, пройдя путь, равный 2, либо из вершины 6, пройдя путь, равный 3. Поэтому справедливо соотношение . В вершину 3 входит только одна стрелка, как раз из вершины 1, и около этой стрелки стоит ее длина, равная 1, следовательно С(3)=1. Поэтому . Поскольку очевидно, что С(6) – положительное число, то из последнего соотношения вытекает, что С(5)=3, то есть вычислять значение С(6) не имеет смысла, поскольку выражение С(6)+3 всегда будет больше 3. В вершину 2 можно попасть либо из вершины 1, пройдя путь, равный 7, либо из вершины 3, пройдя путь, равный 5, либо из вершины 5, пройдя путь, равный 2. Поэтому справедливо соотношение . Очевидно, что С(1)=0. Нам известно, что С(3)=1, С(5)=3. Поэтому Теперь мы можем найти С(4): Таким образом, длина кратчайшего пути равна 8. Из последнего соотношения ясно, что в вершину 4 надо идти через вершину 5. Возвращаясь к вычислению С(5), видим, что в вершину 5 надо идти через вершину 3. А в вершину 3 можно попасть только из вершины 1. Итак, кратчайший путь таков: 1→3→5→4. Задача о кратчайшем пути для исходных данных полностью решена. Варианты заданий Найти кратчайший путь между вершинами 1 и 4 во взвешенном орграфе, заданном таблицей. Вариант №1
Вариант №2
Вариант №3
Вариант №4
Вариант №5
Вариант №6
Вариант №7
Вариант №8
Вариант №9
Вариант №10
Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.) |