Алгоритм Дейкстры

Реферат на тему:

Алгоритм Дейкстры

План:

Введение

• 
  1 Формулировка задачи
  
  • 
    1.1 Примеры
    
  • 
    1.2 Формальное определение
    
• 
  2 Неформальное объяснение
  
  • 
    2.1 Пример
    
• 
  3 Алгоритм
  
  • 
    3.1 Обозначения
    
  • 
    3.2 Псевдокод
    
  • 
    3.3 Описание
    
  • 
    3.4 Доказательство корректности
    
  • 
    3.5 Сложность алгоритма
    
  
  Литература
  Примечания
  

Введение

Алгоритмы поиска на графах
A* B* Алгоритм Беллмана — Форда Двунаправленный поиск Алгоритм Дейкстры Алгоритм Джонсона Поиск в ширину Поиск в глубину Поиск с ограничением глубины Поиск по первому наилучшему совпадению Алгоритм Флойда — Уоршелла

Алгори́тм Де́йкстры (Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.

1. Формулировка задачи

1.1. Примеры

Вариант 1. Дана сеть автомобильных дорог, соединяющих города Московской области. Некоторые дороги односторонние. Найти кратчайшие пути от города Москва до каждого города области (если двигаться можно только по дорогам).
Вариант 2. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A. Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула.