4 года назад
Алгоритм кратчайшего пути Дейкстры
Алгоритм Дейкстры Этот алгоритм был создан учёным из Нидерландов по имени Эдсгер Дейкстр в 1959 году. Он находит наименьший путь от начальной точки графа до конечной. График работает только если граф без рёбер и имеет отрицательный вес. Алгоритм часто применяеться в программировании и других сферах информационных технологиях (в протоколах маршрутизации (OSPF(динамический маршрутизатор) и IS-IS(маршрутизатор промежуточной системы)). Пример задачи. Её решение и объяснение Пускай необходимо отыскать самые короткие дистанции с 1-й вершины в плоть до абсолютно всех других...
337 читали · 1 год назад
Поиск кратчайшего пути в лабиринте
В связи с разработками на тему процедурной генерации дошли руки и до алгоритма поиска кратчайшего пути. Первоначально, по уже забытым причинам, я обозначил его как алгоритм Дейкстры – выдающегося учёного, оказавшего огромное влияние на развитие компьютерной индустрии. Но в комментариях указали, что это волновой алгоритм. Данный алгоритм во-первых очень прост, а во-вторых полезен не только для поиска кратчайшего пути. Он работает на карте, состоящей из клеток. Задача ставится так: если мы находимся...