Главная         Авторы   Статьи   Год проведения   Тематика   Организации        Конференция МЭС

Алгоритмы пересчёта кратчайших путей в графе при изменении весов ребер  

Авторы
 Кривошеин Д.Ю.
 Марченко А.М.
Год публикации
 2012
УДК
 519.17

Аннотация
 В статье рассматривается задача пересчета кратчайших путей в графе при изменении веса какого-либо ребра. При этом можно выделить два принципиально различных случая: увеличение и уменьшение веса ребра. В первом случае описан алгоритм, сложность которого зависит от структуры данного графа и сложности реализации алгоритма Дейкстры для этого графа, при этом для большинства графов сложность ниже, чем сложность алгоритма Флойда-Уоршелла. В случае уменьшения веса ребра описан алгоритм сложности O(n^2).
Ключевые слова
 динамически изменяющийся граф, поиск кратчайших путей, изменение веса ребра, инкрементальный алгоритм
Ссылка на статью
 Кривошеин Д.Ю., Марченко А.М. Алгоритмы пересчёта кратчайших путей в графе при изменении весов ребер // Проблемы разработки перспективных микро- и наноэлектронных систем - 2012. Сборник трудов / под общ. ред. академика РАН А.Л. Стемпковского. М.: ИППМ РАН, 2012. С. 263-266.
Адрес статьи
 http://www.mes-conference.ru/data/year2012/pdf/D171.pdf

Copyright © 2009-2018 ИППМ РАН. All Rights Reserved.

Разработка сайта - ИППМ РАН