Презентация по теме «Алгоритмы на графах» для МДК 01.02 Математический аппарат для построение компьютерных сетей

АЛГОРИТМЫ НА ГРАФАХ МДК 01.02 Математический аппарат для построение компьютерных сетейпреподаватель Скряго О.С. Смоленск 2014 Поиск кратчайших путей в графеПоиск кратчайших путей из вершиныПоиск к.п. между всеми парами вершин 1. ПОИСК КРАТЧАЙШИХ ПУТЕЙ В ГРАФЕ 1. ПОИСК КРАТЧАЙШИХ ПУТЕЙ В ГРАФЕ Варианты задачи поиска кратчайших путей:Кратчайший путь из вершины (из одной вершины во все остальные);Кратчайший путь в заданную вершину (из всех остальных);Кратчайший путь между заданной парой вершин (из заданной вершины в заданную);Кратчайший путь между всем парами вершин (из всех во все). 1. ПОИСК КРАТЧАЙШИХ ПУТЕЙ В ГРАФЕ Основной принцип алгоритмов поиска кратчайших путей:кратчайший путь между двумя вершинами содержит в себе другие кратчайшие пути (кратчайшие пути к промежуточным вершинам). 1. ПОИСК КРАТЧАЙШИХ ПУТЕЙ В ГРАФЕ Кратчайший путь может содержать вершины с отрицательным весом.Если граф имеет цикл с отрицательным весом, который достижим из начальной вершины – алгоритмы могут работать неправильно.Некоторые алгоритмы могут работать с отрицательными весами (Беллман-Форд), некоторые – нет (Дейкстра). 1. ПОИСК КРАТЧАЙШИХ ПУТЕЙ В ГРАФЕ 2. ПОИСК КРАТЧАЙШИХ ПУТЕЙ ИЗ ВЕРШИНЫ 2. ПОИСК КРАТЧАЙШИХ ПУТЕЙ ИЗ ВЕРШИНЫ 2. ПОИСК КРАТЧАЙШИХ ПУТЕЙ ИЗ ВЕРШИНЫ 3. ПОИСК К.П. МЕЖДУ ВСЕМИ ПАРАМИ ВЕРШИН Поиск кратчайшего пути между всеми парами вершин: поиск расстояний от каждой вершины до всех других вершин.Для этого можно V раз выполнить алгоритм Дейкстры, но это вычислительно неоправдано. 3. ПОИСК К.П. МЕЖДУ ВСЕМИ ПАРАМИ ВЕРШИН 3. ПОИСК К.П. МЕЖДУ ВСЕМИ ПАРАМИ ВЕРШИН 3. ПОИСК К.П. МЕЖДУ ВСЕМИ ПАРАМИ ВЕРШИН 3. ПОИСК К.П. МЕЖДУ ВСЕМИ ПАРАМИ ВЕРШИН