4817
правок
Декрементный алгоритм нахождения кратчайших путей между всеми парами: различия между версиями
Перейти к навигации
Перейти к поиску
Декрементный алгоритм нахождения кратчайших путей между всеми парами (посмотреть исходный код)
Версия от 14:15, 20 апреля 2013
, 20 апреля 2013→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Динамический алгоритм на графе поддерживает заданное свойство P графа, подверженного динамическим изменениям – таким как вставка дуги, удаление дуги и обновление веса дуги. | Динамический алгоритм на графе поддерживает заданное свойство '''P''' графа, подверженного динамическим изменениям – таким как вставка дуги, удаление дуги и обновление веса дуги. | ||
Динамический алгоритм должен быстро обрабатывать запросы о свойстве | Динамический алгоритм должен быстро обрабатывать запросы о свойстве '''P''', а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм является [[полностью динамический алгоритм|полностью динамическим]], если он поддерживает как вставку дуг, так и удаление дуг. [[Частично динамический алгоритм]] поддерживает либо вставку, либо удаление дуг; [[инкрементный алгоритм]] поддерживает только вставку дуг, [[декрементный алгоритм|декрементный]] – только удаление. Далее рассматривается декрементная версия алгоритма нахождения кратчайших путей между всеми парами (APSP), которая включает поддержку ориентированного графа с дугами, имеющими вещественные веса, и выполнение последовательности следующих операций в различном порядке: | ||
delete(u, v): удаляет дугу (u ,v) из графа; | delete(u, v): удаляет дугу (u ,v) из графа; | ||
distance(x,y): возвращает значение расстояния от вершины x до вершины y; | distance(x,y): возвращает значение расстояния от вершины x до вершины y; | ||
path(x,y): возвращает кратчайший путь между вершинами x и y, если такой существует. | path(x,y): возвращает кратчайший путь между вершинами x и y, если такой существует. | ||