Описание используемых методов и алгоритмов - Выбор оптимального маршрута для строительства дороги

В данном пункте нужно проанализировать используемый алгоритм поиска кратчайшего пути.

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

Находит кратчайший путь от одной из вершин графа до всех остальных. Алгоритм работает только для графов без ребер отрицательного веса.

Смысл этого способа заключается в том, что обходятся все вершины, начиная с заданной, при этом каждой присваивается метка с некоторым значением. Затем в результат войдут те вершины, метки которых минимальны. На первом шаге исходной вершине присваивается метка со значением 0. Затем рассматриваются все следующие вершины, то есть те, в которые можно попасть из исходной. Им присваиваются метки, значение которых определяется как сумма исходника и веса пути. Из вершин следующего шага выбирается та, что имеет наименьшее значение метки, и изучаются все вершины, в которые из нее можно пройти, не используя промежуточных вершин. Определяется новое значение метки, равное метке вершины - исходника плюс вес пути. Если полученное значение меньше, чем метка вершины, то метка изменяется. В противном случае остается исходное значение. При этом в отдельном массиве, размерность которого равна количеству вершин графа, сохраняется результат оптимизации, по которому и определяется путь.

Главным достоинством алгоритма является простота реализации.

Главным недостатком - то, что по ходу выполнения функции, то есть нахождения кратчайшего пути, алгоритм не может вернуться назад, чтобы пересмотреть другие варианты.

Похожие статьи




Описание используемых методов и алгоритмов - Выбор оптимального маршрута для строительства дороги

Предыдущая | Следующая