Den övre bundet på exponenten,  och, av matris multiplikation över en ring som var tre 1968 har minskat flera gånger och sedan 1986 har det varit 2.376. Å andra sidan, exponenten av algoritmer kända för alla par kortaste vägen problem har stannat på tre alla dessa år även för mycket speciella fall av riktade grafer med enhetliga kant längder. I detta papper ger vi en algoritm av tid O n vs log 3 n, v = (3 +  på)/2, för egglängder i {−1, 0, 1}. Således, för den nuvarande kända bundna på  och vi får en bunden på exponenten, mot < 2.688. När det gäller heltal kant längder med absolut värde som avgränsas ovan av M, är den tid bundet O (M n) mot log 3 n och exponenten är mindre än 3 för M = O (n α ), för α < 0,116 och den ström bundet på  ska.
Alon, Galil och Margalit REF presenterade en algoritm för APSP i riktade grafer med vikter i {-1, 0, 1} av runtimeÕ(n -+3 2 ).
On the Exponent of the All Pairs Shortest Path Problem
{'venue': 'J. Comput. Syst. Sci.', 'journal': 'J. Comput. Syst. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}