Pith. sign in

REVIEW 3 major objections 6 minor 1 references

A New Fast Unweighted All-pairs Shortest Path Search Algorithm Based on Pruning by Shortest Path Trees

T0 review · 3 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read PST, a new all-pairs shortest path algorithm for unweighted graphs, claims that when expanding from a source through a neighbor w the search can traverse only the already-built shortest path tree T(w), reducing average adjacency accesses…

desk verdict Clever BFS-pruning idea for unweighted APSP with consistent speedups on synthetic graphs, but no correctness proof and a termination bug on disconnected graphs; worth a serious referee only if the authors fill those gaps. read the letter →

arxiv 1908.06806 v1 pith:BVLR74A7 submitted 2019-08-19 cs.DS

Yasuo Yamane , Kenichi Kobayashi This is my paper · ORCID
classification cs.DS
keywords all-pairsshortestpathsunweightedgraphsbreadth-firstsearchpathtreepruningadjacencyaccesscountalphahypercube
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proposes PST, an all-pairs shortest path algorithm for unweighted graphs that is meant to be faster than breadth-first search by exploiting shortest path trees. Its central claim is that when a source vertex $v$ reaches a neighbor $w$, every further vertex on a shortest path from $v$ through $w$ lies in the shortest path tree $T(w)$ already built for $w$; therefore PST can traverse only that tree instead of scanning all of $w$'s adjacency. This drops the average number of adjacency accesses per vertex, denoted $\alpha$, from about the average degree of the graph to about 1 in tree-like cases, because a tree has average degree near 2 and only one edge is entered and one exited per visited vertex. Experiments on hypercube and scale-free graphs report $\alpha$ between 1.19 and 1.71 (versus 3.15 to 12.12 for BFS) and CPU time 1.38 to 3.08 times faster at $n = 4096$, with the caveat that dense low-diameter graphs reduce the gain. A sympathetic reader would care because the method is a simple practical improvement for exact distances on unweighted graphs, not a change in worst-case asymptotic complexity.

What carries the argument

The central object is the cor pointer on each t-vertex: a t-vertex $x'$ on $T(v)$ reached through a neighbor's t-vertex $w'$ stores a reference to the corresponding t-vertex $x''$ on $T(w)$, and when extending $T(v)$ one level the algorithm steps through $x''.children$ instead of the graph adjacency list. The second mechanism is the d-queue, a FIFO queue modified to hold $(vertex, distance)$ pairs and to dequeue only pairs at the currently required depth; this makes all shortest path trees grow synchronously, guaranteeing that the needed part of $T(w)$ already exists when $T(v)$ is extended through $w$.

What would settle it

Run PST on a small graph with multiple equal-length shortest paths, such as a 4-cycle with a chord, and compare every entry of the distance matrix $D$ against a plain BFS distance matrix. If any pair has $D[x,v]$ larger than the true distance, or remains marked NOT_SEARCHED, the pruning coverage invariant fails; the same check across many random graphs with heavy tie-breaking would settle whether the tree-based traversal always covers all shortest-path continuations.

Watch

Extended reading notes

Core claim

PST computes exact all-pairs shortest path distances in unweighted graphs by generating every shortest path tree $T(v)$ synchronously, layer by layer, and using the already-generated tree $T(w)$ of each neighbor $w$ as the only region searched when extending $T(v)$ through $w$. Formally, if $\sigma_v(x)$ contains edge $(v,w)$, then $\sigma_v(x)$ can be written as $(v,w)$ plus $\sigma_w(x)$, so no edge outside $T(w)$ needs to be inspected. The algorithm encodes this with a cor pointer: each t-vertex $x'$ in $T(v)$ that was reached through $w'$ points to the corresponding t-vertex $x''$ in $T(w)$, and extension at the next depth iterates over $x''.children$ rather than over the adjacency list of the underlying graph vertex. The paper claims, and measures, that this reduces the average adjacency-access count $\alpha$ to values close to 1 and makes PST faster than BFS on the tested hypercube and scale-free graphs while keeping exact shortest paths.

Load-bearing premise

The load-bearing premise is that every shortest path from a source through a neighbor continues along a shortest path from that neighbor, and that the bookkeeping records all those continuations in the neighbor's tree; if the bookkeeping misses one, PST returns a wrong distance.

Editorial extensions

If this is right

  • If PST is correct, exact all-pairs shortest paths on unweighted graphs can be computed with far fewer adjacency scans than BFS on graphs with large diameter, since $\alpha$ approaches 1 rather than the average degree.
  • The speedup should grow with $n$ on hypercube-like and sparse scale-free graphs; the paper's tables show CPU-time ratios increasing from about 1.6 to about 3.1 as $n$ grows from 64 to 4096.
  • On dense graphs with small diameter, the advantage shrinks because pruning cannot begin at depth 1; the paper's dense scale-free case shows $\alpha$ of 6.23 at $n = 4096$, still 1.95 times lower than BFS.
  • The space cost is higher than BFS: storing t-vertices for every source vertex adds memory beyond the $n \times n$ distance and parent matrices.
  • The paper's $\alpha$-close-to-1 claim is an average over vertices, not a worst-case guarantee, so graph families with many depth-1 vertices will retain a larger constant.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A direct testable extension would run PST on random regular graphs with controlled diameter; the paper's $\alpha$-to-1 mechanism predicts that large-diameter, low-degree graphs give the largest gap over BFS.
  • The pruning idea could be reused for a few-source or single-source setting after a preprocessing pass builds the needed trees, though the paper only presents the all-pairs version.
  • The synchronous d-queue is the likely serial bottleneck; a parallel variant would have to coordinate layer-by-layer extensions across sources, which the paper does not discuss.
  • The cor/children bookkeeping may be sensitive to parent choices inside each $T(w)$; a stress test with many equal-length shortest paths would show whether any tie-breaking regime causes missed vertices.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper proposes PST, a new all-pairs shortest path (APSP) algorithm for unweighted graphs. The algorithm maintains a shortest path tree T(v) for every source v, with parent and child pointers. When expanding a vertex w while building T(v), PST does not scan all neighbors of w; instead, it scans only the children of the corresponding t-vertex in the shortest path tree of the appropriate adjacent vertex, relying on the fact that a partial path of a shortest path is itself shortest. The authors argue that this prunes the search so that the average number of adjacency accesses per vertex, denoted α, is close to 1, whereas for BFS α is approximately the average degree. They report experiments on hypercube-shaped and scale-free graphs with n = 64, 256, 1024, 4096, claiming that PST is faster than BFS in CPU time and has smaller α. The paper includes detailed pseudocode and a discussion of the data structures, but no formal correctness proof and no code or seeds are provided.

Significance. If the pruning invariant is correct, PST is an interesting practical idea for exact unweighted APSP: it could reduce the constant factor of BFS-based APSP on dense-enough shortest-path trees, and the α measure provides a clean way to quantify that reduction. The authors are honest about the space overhead of storing all shortest path trees and about the exclusion of initialization time from CPU measurements. However, the significance is currently limited by the absence of a correctness proof, a termination bug on disconnected graphs, and an experimental section with single measurements and no reproducibility artifacts. The paper is more a preliminary algorithmic proposal than a fully established result.

major comments (3)
  1. [§3.2, PST algorithm pseudocode (while loop and extend)] As written, the outer loop `while 0 < |V|` terminates only when every source has `c == n`. On a disconnected undirected graph, a source in a component of size C < n never reaches `c == n`, so the loop increments `d` forever, and the unreachable entries of `D` remain at the initial value 0.0 instead of infinity. The paper's note that the stopping condition cannot be used for directed graphs does not cover this undirected case. The exact-APSP claim for general unweighted graphs is therefore false as stated; the manuscript should either restrict the claim to connected graphs or modify the loop and distance initialization to handle components and unreachable vertices.
  2. [§3.1 (Pruning by shortest path trees) and §3.2 (extend)] The paper does not prove the coverage invariant that justifies the pruning: at depth d, every undiscovered vertex x at distance d from v is a child of the cor-vertex of some dequeued t-vertex. Section 3.1's 'partial path of a shortest path is also the shortest' argument shows that a vertex on a shortest path through w lies in T(w), but it does not show that the parent chosen in T(w) coincides with the parent chosen in T(v); if the two trees make different parent choices, the pruning could skip x. A formal invariant over the synchronous generation of all T(u) is needed, or the algorithm's exactness on connected graphs is not established.
  3. [§4, Tables 4.1–4.6] The central claim that PST outperforms BFS on speed and α rests on single measurements without error bars, code, seeds, or graph-generation parameters, and the text states that the reported PST CPU time excludes initialization because initialization was bundled with graph creation. Since initialization is excluded only for PST (and for Peng/Dijkstra, not BFS), the speed comparison is not clearly fair; initialization should be included in the reported times or its contribution quantified. The paper should also define α operationally (what exactly counts as one adjacency access) and report multiple runs.
minor comments (6)
  1. [§4.2.2, figures and tables] Figure 4.5 appears twice in the dense scale-free case, and the caption 'Fig.4.5 Comparison in α' should be numbered Fig.4.6; the table labels for this subsection are also duplicated.
  2. [§4.3.1, item 1)] The text says 'BFS’s α is close to 1 in case of hypercube-shaped and sparse scale-free graphs,' but the data in Tables 4.2 and 4.4 show that it is PST's α that is close to 1; BFS's α is several times larger. This appears to be a typo and should be corrected.
  3. [§3.2, reachability note] The note that the stopping condition `c == n` cannot be used for directed graphs should be extended to disconnected undirected graphs, since the same failure occurs there.
  4. [References] The reference list includes [Kim18], which is not cited in the text, and the [BFS] and [Dijkstra] entries are Wikipedia pages rather than standard bibliographic sources; these should be replaced with appropriate citations.
  5. [§4, tables and text] The column headers use '/.PSTw' and '/PST' interchangeably; one consistent notation should be used throughout the tables and text.
  6. [§3.2, pseudocode] Inside `extend`, the line `n = len(D)` shadows the outer variable `n`; renaming this local variable would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No material circularity: PST's pruning derivation rests on the standard shortest-path subpath property and is validated by measurements, not by fitting.

full rationale

The paper's central claim is that PST computes all-pairs shortest paths by traversing only T(w) when extending through an edge (v,w), justified by the standard fact that a subpath of a shortest path is also shortest. This is an independent mathematical property, not an input containing the conclusion. The algorithm constructs T(v) synchronously from previously generated shortest path trees T(w), with the base case at depth 1 handled directly from adjacency lists; there is no fitted parameter later renamed as a prediction, and no quantity is defined in terms of the result it is supposed to establish. The reported alpha values and CPU times are empirical measurements, and the informal explanation that alpha approaches 1 because a tree has average degree about 2 is a heuristic interpretation, not a fitted model used to generate the data. The paper contains no load-bearing self-citation, uniqueness theorem, or imported ansatz: its references are standard textbook sources and prior unrelated work. Therefore, no circular step is present, and the derivation chain is self-contained with respect to the correctness claim. Separately, there may be correctness concerns about disconnected graphs or about proving the pruning coverage invariant, but those are correctness risks, not circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No fitted constants appear in the algorithm; the experimental parameters n and n' are benchmark inputs, not fitted to produce the claimed speedup. The correctness of PST rests on unproved invariants: optimal substructure (standard), completeness of cor-child traversal (ad hoc to the algorithm), synchronous generation of trees (ad hoc to the algorithm), and connectedness for termination. No physical or mathematical entities are postulated; t-vertices and d-queues are data structures internal to the algorithm.

assumptions (4)
  • standard math A partial path of a shortest path is also a shortest path (optimal substructure).
    Invoked in Section 3.1 to justify replacing the remainder of a shortest path through adjacent w by sigma_w(x); true for graphs with nonnegative weights.
  • ad hoc to paper For every vertex y at depth d-1 in T(v), iterating children of the corresponding t-vertex in the shortest path tree of the parent covers all vertices at depth d that have y on some shortest path.
    This completeness is the core of the PST pruning idea; the paper motivates it with the similarity of T(v) and T(w) but does not prove the cor/children bookkeeping is exhaustive.
  • ad hoc to paper Synchronous generation guarantees that when extending T(v) to depth d, the required parts of all shortest path trees of vertices at depth at most d-1 have already been completed.
    Stated in Section 3.1 modification 2 and implemented via d-queues; the invariant is claimed, not proved.
  • domain assumption The termination condition v.c == n assumes every vertex is reachable from v, which holds for connected undirected graphs.
    The paper notes in Section 3.2 that this condition cannot be used for directed graphs because not all vertices are reachable.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A New Fast Unweighted All-pairs Shortest Path Search Algorithm Based on Pruning by Shortest Path Trees." pith.science (2026). https://pith.science/paper/BVLR74A7

@misc{pith2026190806806,
  author       = {Pith},
  title        = {Pith review of: A New Fast Unweighted All-pairs Shortest Path Search Algorithm Based on Pruning by Shortest Path Trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BVLR74A7}},
  note         = {Machine review of arXiv:1908.06806}
}
read the original abstract

We present a new fast all-pairs shortest path algorithm for unweighted graphs. In breadth-first search which is said to representative and fast in unweighted graphs, the average number of accesses to adjacent vertices (expressed by {\alpha}) is about equal to the average degree of the graph. On the other hand, our algorithm utilizes the shortest path trees of adjacent vertices of each source vertex, and reduce {\alpha} drastically. Roughly speaking {\alpha} is reduced to the value close to 1, because the average degree of a tree is about 2, and one is used to come in and the other is used to go out, although that does not hold true when the depth of the shortest path trees is small. We compared our algorithm with breadth-first search algorithm, and our results showed that ours outperforms breadth-first search on speed and {\alpha}.

Figures

Figures reproduced from arXiv: 1908.06806 by the authors.

Figure 3
Figure 3. Fig.3.1(b) [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figure 3
Figure 3. Fig.3.2 Traversing the shortest path tree [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 3
Figure 3. Fig3.3 the data structure of a t [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Comparison in CPU time [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]
Figure 4
Figure 4. Figure 4: Fig.4.4 and Table 4.4 shows the comparison [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]
Figure 4
Figure 4. Figure 4: Comparison in CPU time [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

1 extracted references · 1 canonical work pages

  1. [1]

    Breadth-first search

    [BFS] Wikipedia’s title: “Breadth-first search” [Dijkstra] Wikipedia’s title: Dijkstra’s algorithm . [Floyd62] R . W. Floyd. Algorithm 97: Shortest Path. CACM 5 (6): 345, 1962. [Kim18] J. W. Kim , H. Choi, and S. Bae. Efficient Parallel All-Pairs ShortestPaths Algorithm for Complex Graph Analysis. Proceedings of International Conference on Parallel Proces...

    work page 1962

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.