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

Sanjiang Li, Yongming Li

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$…