4551
правка
Компромиссы при решении динамических графовых задач: различия между версиями
Материал из WEGA
Компромиссы при решении динамических графовых задач (посмотреть исходный код)
Версия от 12:27, 19 июня 2018
, 19 июня 2018→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 167: | Строка 167: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Остается нерешенным фундаментальный вопрос: можно ли решить задачу о нахождении кратчайших путей между всеми парами из определения 3 за время ниже квадратичного на операцию в случае графов с вещественными весами ребер. | Остается нерешенным фундаментальный вопрос: можно ли решить полностью динамическую задачу о нахождении кратчайших путей между всеми парами из определения 3 за время ниже квадратичного на операцию в случае графов с вещественными весами ребер. | ||
== См. также == | == См. также == | ||
