English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Given a directed graph $G$ with arbitrary real-valued weights, the singlesource 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 SSSPalgorithm 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 andvertices in $G$ respectively. In many practical applications, new constraintscome 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 byrigorous proof that the well-known {\sf Ball-String} algorithm for positivelyweighted graphs can be adapted to solve the dynamic SPT problem for directedgraphs with arbitrary weights. Let $n_0$ be the number of vertices that areaffected (i.e., vertices that have different distances from $s$ or differentparents in the input and output SPTs) and $m_0$ the number of edges incident toan 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) orconstructing a new SPT $T'$ for the updated graph. We show by an example thatthe output SPT $T'$ may have more than necessary edge changes to $T$. To remedythis, we give a general method for transforming $T'$ into an SPT with minimaledge changes in time $O(n_0)$ provided that $G$ has no cycles with zero length.

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