Информатика • 11 класс
362
Алгоритм Дейкстры (C++)
- Алгоритм Дейкстры — алгоритм на графах для нахождения кратчайшего пути от одной из вершин графа до всех остальных.
- Описание алгоритма Дейкстры для связного графа.
- Всем вершинам присваивается вес, равный бесконечности.
- Выбирается вершина, от которой будут вычисляться пути до остальных вершин графа, эта вершина объявляется текущей, а её вес – равным 0.
- Вес вершин, соединённых с текущей вершиной ребром, пересчитывается по формуле: вес данной вершины есть минимальное число из старого веса данной вершины, суммы веса текущей вершины и веса ребра, соединяющего текущую вершину с данной.
- В качестве текущей берётся следующая вершина.
- Пункты 3–4 повторяются до тех пор, пока все вершины не будут рассмотрены.
Было полезно?
Рекомендуем
Вы учитель или ученик?
Познакомьтесь с нашим образовательным онлайн-сервисом с тысячами интерактивных работ
Учителю
Удобно проводить уроки в классе, назначать работы на дом и анализировать результаты всего класса или конкретных учеников
Ученику
Самостоятельно изучать новые и повторять пройденные темы, готовиться по индивидуальной траектории и оценивать результаты на наглядных графиках