A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs

摘要

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 O(n~2)n+min{MVT(A_g),MWT(A_G~T)})~1/2 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 O(n~(2.75)).