4488
правок
Алгоритм поиска кратчайших путей между всеми парами в разреженных графах: различия между версиями
Перейти к навигации
Перейти к поиску
м
Алгоритм поиска кратчайших путей между всеми парами в разреженных графах (посмотреть исходный код)
Версия от 00:33, 19 февраля 2012
, 19 февраля 2012→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 53: | Строка 53: | ||
'''Проблема 3'''. Является ли двухточечный алгоритм поиска кратчайших путей более простым, чем алгоритм поиска кратчайших путей между всеми парами, на произвольных взвешенных графах? | '''Проблема 3'''. Является ли двухточечный алгоритм поиска кратчайших путей более простым, чем алгоритм поиска кратчайших путей между всеми парами, на произвольных взвешенных графах? | ||
'''Проблема 4'''. Существует ли алгоритм поиска кратчайших путей между всеми парами со сложностью ниже кубической, т.е. меньше <math>O(n^{3 - \epsilon}) \, </math>?Существует ли алгоритм поиска кратчайших путей между всеми парами со сложностью ниже кубической для графов с целочисленными весами со слабой зависимостью от наибольшего веса дуги C, т.е. исполняющийся за время <math> | '''Проблема 4'''. Существует ли алгоритм поиска кратчайших путей между всеми парами со сложностью ниже кубической, т.е. меньше <math>O(n^{3 - \epsilon}) \, </math>?Существует ли алгоритм поиска кратчайших путей между всеми парами со сложностью ниже кубической для графов с целочисленными весами со слабой зависимостью от наибольшего веса дуги C, т.е. исполняющийся за время <math>O(n^{3 - \epsilon} polylog(C)) \, </math>? | ||