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

A straightforward dynamic programming method for the single-source shortestpaths problem (SSSP) in an edge-weighted directed acyclic graph (DAG) processesthe vertices in a topologically sorted order.  First, we similarly iterate this method alternatively in a breadth-firstsearch sorted order and the reverse order on an input directed graph with bothpositive and negative real edge weights, $n$ vertices and $m$ edges. For apositive integer $t,$ after $O(t)$ iterations in $O(tm)$ time, we obtain foreach vertex $v$ a path distance from the source to $v$ not exceeding thatyielded by the shortest path from the source to $v$ among the so called {\em$t+$light paths}. A directed path between two vertices is $t+$light if itcontains at most $t$ more edges than the minimum edge-cardinality directed pathbetween these vertices. After $O(n)$ iterations, we obtain an $O(nm)$-timesolution to SSSP in directed graphs with real edge weights matching that ofBellman and Ford.  Our main result is an output-sensitive algorithm for the all-pairs shortestpaths problem (APSP) in DAGs with positive and negative real edge weights. Itruns in time $O(\min \{n^{\omega}, nm+n^2\log n\}+\sum_{v\inV}\text{indeg}(v)|\text{leaf}(T_v)|),$ where $n$ is the number of vertices, $m$is the number of edges, $\omega$ is the exponent of fast matrix multiplication,$\text{indeg}(v)$ stands for the indegree of $v,$ $T_v$ is a tree oflexicographically-first shortest directed paths from all ancestors of $v$ to$v$, and $\text{leaf}(T_v)$ is the set of leaves in $T_v.$  Finally, we discuss an extension of hypothetical improved upper time-boundsfor APSP in non-negatively edge-weighted DAGs to include directed graphs with apolynomial number of large directed cycles.

An output-sensitive algorithm for all-pairs shortest paths in directed acyclic graphs