Реализация на VBA алгоритма Форда-Беллмана, алгоритма Дейкстры и алгоритма Левита, по нахождению кратчайших путей Исходная тема с решением находится здесь: http://www.planetaexcel.ru/forum....lt=edit
Постарался детально прокомментировать код, чтобы было понятно Описание алгоритмов, по которым делал решение, взял здесь: http://e-maxx.ru/algo/
Решение сделал с помощью UDF, т.к. UDF возвращает массив, то невсегда будет удобно использовать ее в таком виде, но это легко исправляется макросом, который выводит результат в нужное место и в нужном виде.
Решение Дейкстрой и Левитом находятся в одном файле, т.к. исходные данные (описание графа) одинаковое, и подход к решению очень похожий Граф в решении Форда-Беллмана хранит не матрицу смежности вершин, а описание ребер графа.
Реализация на VBA алгоритма Форда-Беллмана, алгоритма Дейкстры и алгоритма Левита, по нахождению кратчайших путей Исходная тема с решением находится здесь: http://www.planetaexcel.ru/forum....lt=edit
Постарался детально прокомментировать код, чтобы было понятно Описание алгоритмов, по которым делал решение, взял здесь: http://e-maxx.ru/algo/
Решение сделал с помощью UDF, т.к. UDF возвращает массив, то невсегда будет удобно использовать ее в таком виде, но это легко исправляется макросом, который выводит результат в нужное место и в нужном виде.
Решение Дейкстрой и Левитом находятся в одном файле, т.к. исходные данные (описание графа) одинаковое, и подход к решению очень похожий Граф в решении Форда-Беллмана хранит не матрицу смежности вершин, а описание ребер графа.MCH
Сделал еще одну реализацию - алгоритм Дейкстры для разреженного графа Протестировал на реальных данных, данные взял здесь (New York City) Количество точек - 264346 Количество ребер - 733846
Стандартный алгоритм Дейкстры "вешается", не дождался расчтов, оно и понятно асимптотика алгоритма O(n2 + m)
Дейкстра для разрежнного графа на реальных данных показала себя достаточно хорошо, время расчетов в пределах нескольких секунд. Больше всего понравился алгоритм Левита, в виду простой реализации, а также из-за достаточно хорошей скорости. При этом нужно отметить, что алгоритмом Левита находит минимальное расстояние от текущей точки до всех остальных. В алгориме Дйкстры можно ограничить поиск, как только найден путь к необходимой точке, это позволяет ускорить Дейкстру. Если не ограничивать поиск, а искать все пути, то алгортм Декстры в разы медленнее алгоритма Левита.
ЗЫ: В данной рализации изменил формат хранния графа на листе, не в виде матрицы смежности, а описанием ребер: окуда, куда, расстояние ЗЗЫ: У кого-нибуть есть реальные данные по описанию расстояний по карте России? хотелось бы потестировать
Сделал еще одну реализацию - алгоритм Дейкстры для разреженного графа Протестировал на реальных данных, данные взял здесь (New York City) Количество точек - 264346 Количество ребер - 733846
Стандартный алгоритм Дейкстры "вешается", не дождался расчтов, оно и понятно асимптотика алгоритма O(n2 + m)
Дейкстра для разрежнного графа на реальных данных показала себя достаточно хорошо, время расчетов в пределах нескольких секунд. Больше всего понравился алгоритм Левита, в виду простой реализации, а также из-за достаточно хорошей скорости. При этом нужно отметить, что алгоритмом Левита находит минимальное расстояние от текущей точки до всех остальных. В алгориме Дйкстры можно ограничить поиск, как только найден путь к необходимой точке, это позволяет ускорить Дейкстру. Если не ограничивать поиск, а искать все пути, то алгортм Декстры в разы медленнее алгоритма Левита.
ЗЫ: В данной рализации изменил формат хранния графа на листе, не в виде матрицы смежности, а описанием ребер: окуда, куда, расстояние ЗЗЫ: У кого-нибуть есть реальные данные по описанию расстояний по карте России? хотелось бы потестироватьMCH
Сообщение отредактировал MCH - Суббота, 12.10.2013, 11:30
Вход
Регистрация
Напомнить пароль
Автосумма
Часто используемые
ВПР
ЕСЛИ
СУММЕСЛИ
Финансовые
Логические
Текстовые
Даты и времени 
Ссылки и массивы 
Математические
Другие функции
Проверка свойств и значений
Баз данных
Математические
Обработки массивов
Обработки строк
Преобразования типов данных 
Загрузки данных
Работы с файлами
Обработки системных параметров
Обработки цвета
Работы с датами и временем
Преобразования в системы счисления
Финансовые
