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

• 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. Поиск к.п. между всеми парами вершин