Рабочие листы
к вашим урокам
Скачать
1 слайд
Алгоритмы на графах
МДК 01.02 Математический аппарат для построение компьютерных сетей
преподаватель Скряго О.С.
Смоленск 2014
2 слайд
Поиск кратчайших путей в графе
Поиск кратчайших путей из вершины
Поиск к.п. между всеми парами вершин
3 слайд
1. Поиск кратчайших путей в графе
4 слайд
1. Поиск кратчайших путей в графе
Варианты задачи поиска кратчайших путей:
Кратчайший путь из вершины (из одной вершины во все остальные);
Кратчайший путь в заданную вершину (из всех остальных);
Кратчайший путь между заданной парой вершин (из заданной вершины в заданную);
Кратчайший путь между всем парами вершин (из всех во все).
5 слайд
1. Поиск кратчайших путей в графе
Основной принцип алгоритмов поиска кратчайших путей:
кратчайший путь между двумя вершинами содержит в себе другие кратчайшие пути
(кратчайшие пути к промежуточным вершинам).
6 слайд
1. Поиск кратчайших путей в графе
Кратчайший путь может содержать вершины с отрицательным весом.
Если граф имеет цикл с отрицательным весом, который достижим из начальной вершины – алгоритмы могут работать неправильно.
Некоторые алгоритмы могут работать с отрицательными весами (Беллман-Форд), некоторые – нет (Дейкстра).
7 слайд
1. Поиск кратчайших путей в графе
8 слайд
2. Поиск кратчайших путей из вершины
9 слайд
2. Поиск кратчайших путей из вершины
10 слайд
2. Поиск кратчайших путей из вершины
11 слайд
3. Поиск к.п. между всеми парами вершин
Поиск кратчайшего пути между всеми парами вершин: поиск расстояний от каждой вершины до всех других вершин.
Для этого можно V раз выполнить алгоритм Дейкстры, но это вычислительно неоправдано.
12 слайд
3. Поиск к.п. между всеми парами вершин
13 слайд
3. Поиск к.п. между всеми парами вершин
14 слайд
3. Поиск к.п. между всеми парами вершин
15 слайд
3. Поиск к.п. между всеми парами вершин
Рабочие листы
к вашим урокам
Скачать
6 653 607 материалов в базе
Настоящий материал опубликован пользователем Скряго Ольга Сергеевна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материалВаша скидка на курсы
40%Курс профессиональной переподготовки
300 ч. — 1200 ч.
Курс повышения квалификации
72 ч. — 180 ч.
Курс повышения квалификации
36 ч. — 180 ч.
Мини-курс
4 ч.
Мини-курс
4 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.