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

Preprint · Andrzej Lingas, Dzmitry Sledneu

- Archive id: arxiv:1111.6519
- Published: 2011-11-28
- DOI: https://doi.org/10.1007/978-3-642-27660-6_31
- arXiv: https://arxiv.org/abs/1111.6519
- Source URL: https://arxiv.org/abs/1111.6519
- PDF: https://arxiv.org/pdf/1111.6519
- Provenance: arxiv

## Abstract

We consider the problem of computing all-pairs shortest paths in a directed graph with real weights assigned to vertices. For an $n\\times 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 nonnegative 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. $\\widetilde{O}(n^{2}\\sqrt {n + \\min\\{MWT(A\_G), MWT(A\_G^t)\\}})$ We also conclude that the all-pairs shortest path problem for uniform disk graphs, with nonnegative real vertex weights, induced by point sets of bounded density within a unit square can be solved in time $\\widetilde{O}(n^{2.75})$.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.