Let G = (V, E, w) be a weighted directed graph, where w : E /spl rarr/ {-M, ..., 0, ..., M}. We show that G can be preprocessed in O/spl tilde/(Mn/sup /spl omega//) time, where /spl omega/   n/sup /spl omega/- 1/2 / /spl sime/ n/sup 1.876/.
['Raphael Yuster', 'Uri Zwick']
Answering distance queries in directed graphs using fast matrix multiplication