4501
правка
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения (посмотреть исходный код)
Версия от 18:41, 23 января 2012
, 23 января 2012нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 73: | Строка 73: | ||
Среди оставшихся нерешенными задач особенно выделяются две. Первая заключается в уменьшении сложности <math>\tilde{O}(n^{2.575}) \, </math> при нахождении кратчайших путей между всеми парами вершин графа с дугами единичной стоимости. Вторая состоит в улучшении границы <math>M < O(n^{0.624}) \, </math> сложности алгоритма нахождения кратчайших путей между всеми парами вершин графа, стоимости дуг которого являются целыми числами не более M, и достижении значений ниже кубических. | Среди оставшихся нерешенными задач особенно выделяются две. Первая заключается в уменьшении сложности <math>\tilde{O}(n^{2.575}) \, </math> при нахождении кратчайших путей между всеми парами вершин графа с дугами единичной стоимости. Вторая состоит в улучшении границы <math>M < O(n^{0.624}) \, </math> сложности алгоритма нахождения кратчайших путей между всеми парами вершин графа, стоимости дуг которого являются целыми числами не более M, и достижении значений ниже кубических. | ||
== | == См. также == | ||
Литература | * ''[[Алгоритм поиска кратчайших путей в разреженных графах]]'', | ||
1. Alon, N., Galil, Z., Margalit, O.: On the exponent of the all pairs shortest path problem. In: Proc. 32th IEEE FOCS, pp. 569-575. | |||
* ''[[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами]]'' | |||
== Литература == | |||
1. Alon, N., Galil, Z., Margalit, O.: On the exponent of the all pairs shortest path problem. In: Proc. 32th IEEE FOCS, pp. 569-575. | |||
IEEE Computer Society, Los Alamitos, USA (1991). Also JCSS 54, 255-262(1997) | IEEE Computer Society, Los Alamitos, USA (1991). Also JCSS 54, 255-262(1997) | ||
2. Alon, N., Galil, Z., Margalit, O., Naor, M.: Witnesses for Boolean matrix multiplication and for shortest paths. In: Proc. 33th IEEE FOCS, pp. 417 | |||
3. Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9, 251-280 (1990) | 2. Alon, N., Galil, Z., Margalit, O., Naor, M.: Witnesses for Boolean matrix multiplication and for shortest paths. In: Proc. 33th IEEE FOCS, pp. 417-426. IEEE Computer Society, Los Alamitos, USA (1992) | ||
4. Coppersmith, D.: Rectangular matrix multiplication revisited. J. Complex. 13,42 | |||
5. Huang, X., Pan, V.Y.: Fast rectangular matrix multiplications and applications. J. Complex. 14, 257-299 (1998) | 3. Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9, 251-280 (1990) | ||
6. Romani, F.: Shortest-path problem is not harder than matrix multiplications. Info. Proc. Lett. 11,134-136 (1980) | |||
7. Seidel, R.: On the all-pairs-shortest-path problem. In: Proc. 24th ACM STOC pp. 745-749. Association for Computing Machinery, New York, USA (1992) Also JCSS 51,400 | 4. Coppersmith, D.: Rectangular matrix multiplication revisited. J. Complex. 13,42-49(1997) | ||
8. Schonhage, A., Strassen, V.: Schnelle Multiplikation GroRerZahlen. Computing 7, 281-292 (1971) | |||
9. Takaoka, T.: Sub-cubic time algorithms for the all pairs shortest path problem. Algorithmica 20, 309-318 (1998) | 5. Huang, X., Pan, V.Y.: Fast rectangular matrix multiplications and applications. J. Complex. 14, 257-299 (1998) | ||
6. Romani, F.: Shortest-path problem is not harder than matrix multiplications. Info. Proc. Lett. 11,134-136 (1980) | |||
7. Seidel, R.: On the all-pairs-shortest-path problem. In: Proc. 24th ACM STOC pp. 745-749. Association for Computing Machinery, New York, USA (1992) Also JCSS 51,400-403 (1995) | |||
8. Schonhage, A., Strassen, V.: Schnelle Multiplikation GroRerZahlen. Computing 7, 281-292 (1971) | |||
9. Takaoka, T.: Sub-cubic time algorithms for the all pairs shortest path problem. Algorithmica 20, 309-318 (1998) | |||
10. Zwick, U.: All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM 49(3), 289-317 (2002) | 10. Zwick, U.: All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM 49(3), 289-317 (2002) | ||