We consider the problem of computing all-pairs shortest paths in a directed graph with non-negative real weights assigned to vertices.

For an *n*×*n* 0 − 1 matrix *C*, let *K*_{C} be the complete weighted graph on the rows of *C* where the weight of an edge between two rows is equal to their Hamming distance. Let *MWT*(*C*) be the weight of a minimum weight spanning tree of *K*_{C}.

We show that the all-pairs shortest path problem for a directed graph *G* on *n* vertices with non-negative real weights and adjacency matrix *A*_{G} can be solved by a combinatorial randomized algorithm in time
$$\widetilde{O}(n^{2}\sqrt{n + \min\{MWT(A_G), MWT(A_G^t)\}})$$
As a corollary, we conclude that the transitive closure of a directed graph *G* can be computed by a combinatorial randomized algorithm in the aforementioned time.

We also conclude that the all-pairs shortest path problem for vertex-weighted uniform disk graphs induced by point sets of bounded density within a unit square can be solved in time
$\widetilde{O}(n^{2.75})$
.