Нахождение кратчайшее расстояние в взвешенном графе на ABAP. Алгоритм Дейкстры.

В базе данных HANA есть возможность работать с графами. Есть WEB-визуализатор. Если говорить грубо, то при создании графа в HANA, мы создаем объект похожий на Calculation view. Если задача стоит найти кратчайшее расстояние эффективным способом, то тут могут возникнуть проблемы. Как выяснилось, алгоритм из коробки работает медленнее чем, написанный на ABAP. (С версии, кажется, SP2 есть модификация алгоритма в HANA для нахождения кратчайшего расстояния one-to-one, а не one-to-all, но проверить его я не могу)

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

Алгоритм Дейкстры входит в университетский курс «Теории графов», так что заострять внимание на его работе в этой статье я не буду. Тем более в интернете есть масса источников. Из особенностей можно выделить, что мы ищем кратчайшее расстояние от одной вершины ко всем.

Инициализация

Таблица для хранения ребер ZSTATION_EDGES

Таблица содержит 27.328 записей, инициализировать вершины в этом алгоритме я не буду, вершины будут «набираться» по ходу расчета. Количество вершин составляет 13.371. Логику расчета я вынес в функциональный модуль, подпрограммы не используются для ускорения расчета.

Импорт модуля

Экспорт модуля

Структура ZROUSTE_T

Реализация алгоритма Дейкстры

На этом этапе в chekedNodes находятся кратчайшие маршруты от START_NODE до всех вершин.

Пример маршрута (поле PATH)

Так как мы ищем расстояние между двумя вершинами, то соберем ответ.

Результат на тестовых вершинах, на изменяемые параметры можно не обращать внимание

Часть ответа

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

Весь код можно посмотреть в GIT.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *