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