1.1 Анализ задания
Волновой алгоритм -- алгоритм, позволяющий найти минимальный путь в графе с рёбрами единичной длины. Основан на алгоритме поиска в ширину. Применяется для нахождения кратчайшего пути в графе, в общем случае находит лишь его длину.
Суть алгоритма следующая:
1. Указываются вершины первого фронта - смежные с начальной точкой пути. Им приписывается метка 1.
2. Вершинам следующего фронта - смежным с вершинами предыдущего - приписывается метка на один больше.
3. Если во фронте не достигнута конечная точка пути, и есть неразмеченные вершины, смежные с текущим фронтом, то повторяется шаг 2. Иначе выполняется шаг 4.
4. Если во фронте достигнута конечная точка пути, то длина кратчайшего пути составит значение метки фронта, к которому она принадлежит. Если нет неразмеченных вершин, смежных с текущим фронтом, то конечная точка пути недостижима из начальной (бесконечно далека).
С помощью волнового алгоритма можно рассчитать основные метрические характеристики графа - диаметр и радиус.
Расстояние от данной вершины a до наиболее удаленной от нее вершины называется эксцентриситетом вершины a и обозначается через ecc(a).
Величина наименьшего эксцентриситета называется радиусом графа и обозначается через rad(G), а величина наибольшего - диаметром и обозначается diam(G).
Наименьший диаметр имеет полный граф - его диаметр равен 1. Среди связных графов с n вершинами наибольший диаметр, равный n-1, имеет цепь Pn .
Разметив граф волновым алгоритмом поочередно от каждой вершины, можно определить ее эксцентриситет, а из множества всех эксцентриситетов графа установить его радиус и диаметр.
- Введение
- 1. Анализ задания и обзор аналогов
- 1.1 Анализ задания
- 1.2 Обзор аналогов
- 2. Сценарий работы пользователя
- 2.2 Сценарий работы пользователя
- 3. Архитектура программного кода
- 4.1 Формат ответа
- 4.2 Формат тестового набора
- 5. Виртуальный стенд
- 6. Проверяющий сервер
- 7. Задания и тестовые наборы
- Заключение
- Описание виртуальной лаборатории Начало работы в виртуальной лаборатории
- Минимальные маршруты в нагруженных графах
- «Исследование работы счетчиков на триггерах в виртуальной лаборатории»
- Виртуальные экскурсии – эффективный инновационный инструмент совершенствования технологической подготовки обучающихся Каунов а.М., Фетелава т.А.
- Глава 1 обзор виртуальных лабораторий
- 4.1.4 Поиск оптимального маршрута
- Приложение Виртуальная измерительная лаборатория.
- Настройка таблицы маршрутов
- Виртуальная лаборатория пцр Виртуальное определение бактерий
- Выделение маршрутов