4824
правки
Полностью динамический алгоритм достижимости с единственным источником: различия между версиями
Перейти к навигации
Перейти к поиску
м
Полностью динамический алгоритм достижимости с единственным источником (посмотреть исходный код)
Версия от 03:30, 20 февраля 2018
, 20 февраля 2018→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Динамический алгоритм на графе поддерживает заданное свойство P графа, подверженного динамическим изменениям – таким как вставка ребра, удаление ребра и обновление веса ребра. Динамический алгоритм должен быстро обрабатывать запросы о свойстве P, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм является полностью динамическим, если он поддерживает как вставку ребер, так и удаление, и частично динамическим, если поддерживает либо вставку, либо удаление ребер. | Динамический алгоритм на графе поддерживает заданное свойство <math>\mathcal{P}</math> графа, подверженного динамическим изменениям – таким как вставка ребра, удаление ребра и обновление веса ребра. Динамический алгоритм должен быстро обрабатывать запросы о свойстве <math>\mathcal{P}</math>, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм является ''полностью динамическим'', если он поддерживает как вставку ребер, так и удаление, и ''частично динамическим'', если поддерживает либо вставку, либо удаление ребер. | ||