Answering distance queries in directed graphs using fast matrix multiplication
Raphael Yuster, Uri Zwick · 2005
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/.