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


Download 23.87 Kb.
bet1/4
Sana28.03.2023
Hajmi23.87 Kb.
#1302212
TuriРеферат
  1   2   3   4
Bog'liq
Алгоритм Дейкстры


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

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



План:


    Введение

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

  • 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. Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула.

Download 23.87 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling