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 x 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 short