4824
правки
Полностью динамический алгоритм нахождения кратчайших путей между всеми парами: различия между версиями
Перейти к навигации
Перейти к поиску
Полностью динамический алгоритм нахождения кратчайших путей между всеми парами (посмотреть исходный код)
Версия от 06:25, 25 мая 2014
, 25 мая 2014→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 7: | Строка 7: | ||
В задаче нахождения кратчайших путей между всеми парами (APSP) необходимо поддерживать ориентированный граф G = (V, E) с дугами, имеющими вещественные веса, и выполнение последовательности следующих операций в различном порядке: | В задаче нахождения кратчайших путей между всеми парами (APSP) необходимо поддерживать ориентированный граф G = (V, E) с дугами, имеющими вещественные веса, и выполнение последовательности следующих операций в различном порядке: | ||
Update(x, y, w): обновление веса дуги (x, y) с присвоением вещественного значения w; эта операция включает в качестве специальных случаев вставку дуги (если вес меняется с +1 на w < +1) и удаление дуги (если вес устанавливается равным w = +1); | |||
Distance(x, y): | '''Update(x, y, w)''': обновление веса дуги (x, y) с присвоением вещественного значения w; эта операция включает в качестве специальных случаев вставку дуги (если вес меняется с +1 на w < +1) и удаление дуги (если вес устанавливается равным w = +1); | ||
Path(x, y): возвращает кратчайший путь между x и y, если таковой существует. | |||
'''Distance(x, y)''': возвращает кратчайшее расстояние от x до y. | |||
'''Path(x, y)''': возвращает кратчайший путь между x и y, если таковой существует. | |||
Более формально эту задачу можно определить следующим образом. | Более формально эту задачу можно определить следующим образом. | ||
Задача 1 (Полностью динамический алгоритм нахождения кратчайших путей между всеми парами) | Задача 1 (Полностью динамический алгоритм нахождения кратчайших путей между всеми парами) | ||
Дано: взвешенный ориентированный граф G = (V, E) и вышеописанная последовательность операций. | |||
Требуется: найти матрицу D, такую, что ячейка матрицы D[x, y] хранит расстояние между вершинами x и y на протяжении всей последовательности операций. | '''Дано''': взвешенный ориентированный граф G = (V, E) и вышеописанная последовательность операций. | ||
'''Требуется''': найти матрицу D, такую, что ячейка матрицы D[x, y] хранит расстояние между вершинами x и y на протяжении всей последовательности операций. | |||