# Semi-dynamic shortest-path tree algorithms for directed graphs with arbitrary weights

Preprint · Sanjiang Li, Yongming Li

- Archive id: arxiv:1903.01756
- Published: 2019-03-05
- arXiv: https://arxiv.org/abs/1903.01756
- Source URL: https://arxiv.org/abs/1903.01756
- PDF: https://arxiv.org/pdf/1903.01756
- Provenance: arxiv

## Abstract

Given a directed graph $G$ with arbitrary real-valued weights, the single source shortest-path problem (SSSP) asks for, given a source $s$ in $G$, finding a shortest path from $s$ to each vertex $v$ in $G$. A classical SSSP algorithm detects a negative cycle of $G$ or constructs a shortest-path tree (SPT) rooted at $s$ in $O(mn)$ time, where $m,n$ are the numbers of edges and vertices in $G$ respectively. In many practical applications, new constraints come from time to time and we need to update the SPT frequently. Given an SPT $T$ of $G$, suppose the weight on a certain edge is modified. We show by rigorous proof that the well-known {\\sf Ball-String} algorithm for positively weighted graphs can be adapted to solve the dynamic SPT problem for directed graphs with arbitrary weights. Let $n\_0$ be the number of vertices that are affected (i.e., vertices that have different distances from $s$ or different parents in the input and output SPTs) and $m\_0$ the number of edges incident to an affected vertex. The adapted algorithms terminate in $O(m\_0+n\_0 \\log n\_0)$ time, either detecting a negative cycle (only in the decremental case) or constructing a new SPT $T'$ for the updated graph. We show by an example that the output SPT $T'$ may have more than necessary edge changes to $T$. To remedy this, we give a general method for transforming $T'$ into an SPT with minimal edge changes in time $O(n\_0)$ provided that $G$ has no cycles with zero length.

_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.