Логотип
О сервисе
Войти
Информатика • 11 класс
Просмотрено68

Алгоритм Дейкстры (C++)

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

 

Было полезно?

Рекомендуем

Получите бесплатный доступ к сервису «Облако знаний»
  • тысячи интерактивных работ
  • обновлённый контент по ФГОС
  • свежие варианты ОГЭ/ЕГЭ
  • опорные конспекты по всем предметам

Это и многое другое доступно после входа через Educont.ru

Войти через Educont.ru

Если у вас нет доступа к Educont.ru, зарегистрируйтесь, а затем активируйте классу бесплатный доступ к контенту «Облако знаний».

Материалы - Облако знаний
Логотип облако знаний
+7 (499) 322-07-57
info@oblakoz.ru

Контактный центр

МО, г. Долгопрудный, Лихачевский проезд, 4, стр. 1

Отдел заботы о пользователях

Следите за нами:
Группа телеграм облако знанийТелеграмГруппа вконтакте облако знанийВКонтакте
Политика конфиденциальности

© ООО «Физикон Лаб», 2022