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