Информатика • 11 класс
417

Алгоритм Дейкстры (Паскаль)

  • Алгоритм Дейкстры — алгоритм на графах для нахождения кратчайшего пути от одной из вершин графа до всех остальных.
  • Описание алгоритма Дейкстры для связного графа.
    1. Всем вершинам присваивается вес, равный бесконечности.
    2. Выбирается вершина, от которой будут вычисляться пути до остальных вершин графа, эта вершина объявляется текущей, а её вес равным 0.
    3. Вес вершин, соединённых с текущей вершиной ребром, пересчитывается по формуле: вес данной вершины есть минимальное число из старого веса данной вершины, суммы веса текущей вершины и веса ребра, соединяющего текущую вершину с данной.
    4. В качестве текущей берётся следующая вершина.
    5. Пункты 34 повторяются до тех пор, пока все вершины не будут рассмотрены.
Изображение 1
Было полезно?

Рекомендуем

Вы учитель или ученик?
Познакомьтесь с нашим образовательным онлайн-сервисом с тысячами интерактивных работ
Учителю
Удобно проводить уроки в классе, назначать работы на дом и анализировать результаты всего класса или конкретных учеников
Ученику
Самостоятельно изучать новые и повторять пройденные темы, готовиться по индивидуальной траектории и оценивать результаты на наглядных графиках
Зарегистрироваться в «Облаке знаний»