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