Полностью динамический алгоритм нахождения кратчайших путей между всеми парами: различия между версиями

Недавние исследования в области динамических алгоритмов нахождения кратчайших путей поставили новые и весьма интересные вопросы. Можно ли уменьшить объем памяти, необходимой динамическому алгоритму нахождения кратчайших путей, до O(n2)? Возможно, еще более важный вопрос заключается в том, можно ли эффективно решить полностью динамическую задачу достижимости и нахождения кратчайших путей с единственным источником на графах общего вида? Наконец, существуют ли техники общего вида, позволяющие сделать полностью динамическими алгоритмы, использующие только приращение? Подобные техники широко использовались в случае полностью динамических алгоритмов на неориентированных графах [11, 12, 13].