ребру e графа приписано положительное число – длина ребра L(e).
Задача заключается в нахождении маршрута от вершины a к вершине b, наименьшей длины.
Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Дискретная математика
Содержание
Задача о кратчайшем путиПусть G =(V, E) – н-граф.Пусть каждому ребру e графа приписано положительное число – длина ребра L(e). Задача заключается в нахождении маршрута от вершины a к вершине b,
Слайды и текст этой презентации
Слайд 2Задача о кратчайшем пути
Пусть G =(V, E) – н-граф.
Пусть каждому
Задача заключается в нахождении маршрута от вершины a к вершине b, наименьшей длины.
Слайд 3Алгоритм
Присвоим всем вершинам метки s(v)=+∞, причем метка s(а)=0
Проверим каждое ребро
(vi , vj) на выполнение условия:
s(vj) - s(vi) > L(vi
, vj). Если это так, пересчитаем метку конца ребра: s(vj) = s(vi)+L(vi , vj).
Слайд 4Алгоритм
Совершаем пересчет меток до тех пор, пока не перестанет выполнятся
указанное условие. Метка, которую получила вершина b является длиной искомого
маршрута.
