Программные продукты и системы

Графовые модели широко используются при анализе и синтезе систем сложной структуры, особенно сильно связанных. Программные средства решения данных задач, а также методы визуализации свойств графовых структур широко применяются как в прикладных пакетах общего назначения, так и в специализированных системах, например, Intelligent Graph Visualizer, Visual Graph, WEGA и др.

Одной из наиболее распространенных задач на графовых моделях является построение во взвешенном графе маршрута между двумя заданными вершинами, обладающего минимальной стоимостью – суммой весов входящих в него ребер. В случае ребер неотрицательного веса для поиска точного решения оптимальным является алгоритм Дейкстры. Однако данный алгоритм нельзя применять в случае наличия ребер отрицательного веса, поскольку в ряде случаев, например, при наличии ребер отрицательного веса, инцидентных стартовой вершине, он не находит даже приближенных решений. Ребра отрицательного веса характерны для экономических задач, в которых выполнение отдельных операций может приносить не только прибыль, но и убытки.

Рекомендуемый для решения этой задачи алгоритм Беллмана–Форда, как показывает анализ, даже при самой глубокой модификации гарантирует получение только приближенных решений. Поскольку точное определение минимального пути в графах с ребрами отрицательного веса является актуальной задачей в целом ряде областей, особенно в экономике, в работе рассмотрен алгоритм, гарантированно дающий искомое решение. Его применение может устранить данный существенный пробел в современных программных графовых системах.

Основная проблема графов с отрицательными весами ребер – так называемые отрицательные циклы, в которых сумма весов ребер отрицательна. Исследование данных циклов представляет собой отдельную задачу, для решения которой применяется алгоритм Флойда–Уоршелла. Исследованию их в динамических графах посвящена работа.

Подробное описание дается в статье «Точное решение задачи поиска минимального ациклического пути во взвешенных графах, содержащих ребра отрицательного веса», авторы: Н.И. Гданский (Московский политехнический университет, г. Москва), Н.Л. Куликова (Национальный исследовательский университет «Московский энергетический институт», г. Москва), Е.В. Чумакова (Московский авиационный институт (национальный исследовательский университет), г. Москва).