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

Среди оставшихся нерешенными задач особенно выделяются две. Первая заключается в уменьшении сложности <math>\tilde{O}(n^{2.575}) \, </math> при нахождении кратчайших путей между всеми парами вершин графа с дугами единичной стоимости. Вторая состоит в улучшении границы <math>M < O(n^{0.624}) \, </math> сложности алгоритма нахождения кратчайших путей между всеми парами вершин графа, стоимости дуг которого являются целыми числами не более M, и достижении значений ниже кубических.