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