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

Kenichi Kobayashi; Yasuo Yamane

REVIEW 4 major objections 3 minor 1 references

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

T0 review · 4 major / 3 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 A tree-pruned all-pairs shortest path algorithm for weighted graphs cuts average vertex scans to near one and is proven deadlock-free under positive edge weights.

desk verdict A genuine weighted-graph adaptation of the authors' PST pruning idea with honest experiments, but the deadlock-freeness proof is flawed and correctness is never established. read the letter →

arxiv 1908.06798 v1 pith:LAU5RG6E submitted 2019-08-19 cs.DS

Yasuo Yamane , Kenichi Kobayashi This is my paper · ORCID

classification cs.DS

keywords all-pairsshortestpathsweightedgraphspathtreespruningdeadlock-freenesspriorityqueuesscale-freehypercube

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

PSTw is a proposed all-pairs shortest path algorithm for positive-weight undirected graphs. It claims that when a search from a source reaches a neighboring vertex w, only w's shortest path tree needs to be traversed, not all of w's incident edges; by generating all root-to-vertex shortest path trees synchronously, the average number of adjacent-vertex accesses per vertex drops from about the graph's average degree to roughly 2, and close to 1 when trees are deep. The paper proves that despite the waiting steps needed for synchronization, the algorithm cannot deadlock if all edge weights are positive. On hypercube-shaped and dense scale-free graphs the paper reports PSTw faster than the standard all-pairs method, with much smaller average vertex access counts; against the reuse-based variant, PSTw wins on hypercube-shaped and dense scale-free graphs but loses on sparse scale-free graphs.

What carries the argument

The object that carries the argument is the shortest path tree of an adjacent vertex, stored as a network of t-vertices. A t-vertex represents one vertex in one source's tree and carries a parent, children, an 'is_determined' flag, and a 'cor' pointer to the corresponding t-vertex in the neighboring source's tree; when extending from source $v_i$ through neighbor $w$, the loop reads only the children of the counterpart of $w$ in $T(w)$, pruning everything else. Synchrony is enforced by giving every vertex a priority queue: a dequeued t-vertex whose counterpart in the neighbor tree is not yet determined is enqueued again later, and the tree is extended only when the counterpart's children exist. The deadlock-freeness proof is carried by a summation identity around any purported waiting cycle, $\sum e_i \le 0$, which is impossible for positive weights.

What would settle it

Run PSTw on a small positive-weight graph with a three-vertex cycle where each vertex waits on the next, choosing edge weights and target vertices so that the key inequality $e_{i+1}+d_{i+2}\le d_{i+1}$ fails for every $i$ in the cycle; if the graph computation still terminates, the theorem is true but the stated proof reason is not the right one, and if it does not terminate, the theorem is false.

Watch

Extended reading notes

Core claim

The paper's central claim is that the all-pairs shortest path problem on positive-weight undirected graphs can be solved by a synchronous, tree-pruned extension of the standard label-setting algorithm. For a source $v_i$, the algorithm does not scan every edge of every settled vertex; when the search passes through a neighbor $w$, it traverses only the children of the corresponding node in $w$'s shortest path tree $T(w)$, using a 'cor' pointer that links each node in $v_i$'s tree to its counterpart in $w$'s tree. Because these trees are generated together in rounds, a vertex may find the needed children not yet built and must re-enqueue the waiting vertex, which raises the question of deadlock. The paper's Theorem states that if all edge weights are positive, no deadlock can occur: a cycle of waiting vertices would imply the sum of edge weights around the cycle is $\le 0$, contradicting positivity. Empirically the paper reports that this construction reduces the average number of adjacent-vertex accesses to about 2 on hypercube graphs and close to 1 on sparse scale-free graphs, and that it is faster than the two comparison algorithms on hypercube-shaped and dense scale-free graphs, though not on sparse scale-free graphs.

Load-bearing premise

The deadlock-freeness proof relies on the assumption that if one vertex is enqueued before another in a neighbor's priority queue, the path through the first vertex is no longer than the distance to the second; priority-queue order does not actually guarantee that, so the key inequality is unsupported.

Editorial extensions

If this is right

On graphs with deep shortest path trees, the average number of adjacent-vertex accesses per source becomes near 2, close to the information-theoretic minimum for traversing a tree.
At the largest tested size ($n=4096$), the paper reports speedups of about 2.0 times over the standard all-pairs method on hypercube graphs and about 5.4 times on dense scale-free graphs.
The deadlock-free property means the wait-and-retry scheduling needs no timeout or rollback mechanism for positive weights.
In sparse scale-free graphs, the paper reports the reuse-based variant retains a large advantage (at $n=4096$, factor 5 in CPU time), so the new algorithm is not uniformly dominant.
The extra tree and per-vertex queue storage makes the algorithm's space usage larger than the two comparison methods, which need only the distance and parent matrices.

Reading between the lines

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

The synchronous wait-and-re-enqueue structure suggests the algorithm would map naturally onto parallel or distributed execution, with each source's tree advancing in rounds; the paper only reports serial runs.
The reported comparison metric counts adjacent-vertex accesses differently across algorithms (the comparison variant's $\alpha$ is reported as low as 0.02), so the $\alpha$ comparisons are not directly interpretable as 'work per vertex' without accounting for the definition.
A natural extension is to directed graphs or zero-weight edges; zero-weight edges would break the strict positivity used in the deadlock proof, so such cases need separate treatment.

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.

Desk Editor's Note

read the letter

The short version: this is a plausible engineering extension of their unweighted PST idea to weighted graphs, and the reported speedups on hypercube and dense scale-free graphs are worth a look. But the only formal guarantee they claim is not proved, and correctness of the algorithm is not proved at all. I would not accept it in this form, but I would engage with the idea.

What's new: the waiting and suspension mechanism is a real adaptation to weighted graphs, and the deadlock problem is a genuine issue that does not arise in PSTu. The empirical comparison is honest—they report losing to Peng by 5x on sparse scale-free graphs as well as winning elsewhere—and the α metric is a useful diagnostic. The paper also correctly notes the space complexity disadvantage of storing full trees per source.

Where it comes apart: the stress-test note is right. The deadlock-free proof in §3.3 rests on the inequality e_{i+1}+d_{i+2} ≤ d_{i+1}, justified by enqueue order. But the priority queue orders by tentative keys, which are upper bounds, not final distances. Since the algorithm allows updates to already-enqueued vertices, a vertex can be dequeued with a key that is not its true distance. So the inequality does not follow, and the summation argument gives no contradiction. Separately, even if PSTw always terminates, the paper never proves that the computed D matrix equals the true all-pairs distances, or that a vertex's children are never generated after it has been settled. The pseudo-code also has undefined identifiers (w'' and edge_len in the waiting branch) and inconsistent use of x' vs x''. Those are fixable, but they make verification harder.

The evaluation is a real soft spot in a different way: no error bars, no repeated runs, no code release. The CPU times are plausible, but we only have the reported numbers. For a paper claiming both correctness and speed, a correctness check against a known implementation would be a minimal addition.

Who this is for: someone working on practical all-pairs shortest paths for dense or regular graphs might get useful ideas, especially the α metric and the observation about where Peng's sorting-by-degree trick pays off. But a reader needs to treat the performance claims as provisional.

My recommendation: this deserves a serious referee, not a desk rejection, because the core idea is novel and the flaw in the proof is specific and possibly repairable. But in the current form I would not accept it; the authors need to fix the deadlock-freeness proof or replace it with a termination/correctness argument, clean up the pseudo-code, and release code or at least add verification runs.

Referee Report

4 major / 3 minor

Summary. The manuscript proposes PSTw, a weighted all-pairs shortest path algorithm that prunes the search space by using the shortest path trees of adjacent vertices. It presents a deadlock-freeness theorem in §3.3, and reports an experimental comparison against Dijkstra's algorithm and Peng's algorithm on hypercube-shaped and scale-free graphs, measuring wall-clock time and an average adjacency-access count alpha. The central claims are that PSTw is correct (deadlock-free and computes all shortest paths) and that it outperforms Dijkstra in most cases and Peng on hypercube and dense scale-free graphs.

Significance. If PSTw were correct and as fast as reported, it would be a valuable alternative for all-pairs shortest path computation on large graphs, achieving alpha values close to 1 in several graph families. The experimental design covers multiple graph shapes and sizes, and the authors honestly discuss the space-complexity overhead and the deadlock risk. However, the correctness of the distance matrix is never proven, and the only formal guarantee attempted, the deadlock-freeness theorem, relies on an unjustified inequality. The contribution is therefore not established at the level expected for an algorithms paper.

major comments (4)

[§3.3] The proof of deadlock-freeness uses the inequality e_{i+1}+d_{i+2} <= d_{i+1}, justified by the claim that x_{i+2} was enqueued before x_{i+1} in the priority queue. The priority queue orders by tentative (known) distances, which are upper bounds, not by the true final distances d_{i+1} and d_{i+2} that appear in the inequality. The path from v_{i+1} to x_{i+2} through v_{i+2} can be longer than the true distance to x_{i+1}. Without this inequality, the summation argument that yields sum e_i <= 0 collapses, so the theorem is not proved.
[§3.2] The pseudo-code for extend() contains undefined identifiers in the else branch: w'' is used before any definition (presumably w'.cor), and the re-enqueued pair at the marked line (*) uses edge_len, which is not the distance that was dequeued, instead of the correct variable. Additionally, the loop iterates over x'' in w''.children but references x'.vertex before x' has been assigned in the NOT_SEARCHED branch, making the code ambiguous and not directly executable.
[§3 overall] The paper proves only deadlock-freeness, but it does not prove that PSTw terminates with D[i,j] equal to the true shortest distance from v_i to v_j, nor does it prove that the pruning by shortest path trees never discards a necessary path. Even if the deadlock argument were repaired, the key property of an all-pairs shortest path algorithm, correctness of the returned distances, remains unproven.
[§4] The evaluation reports a single CPU time and a single alpha value for each combination of algorithm, graph family, and size, with no repeated runs, no variance measures, and no check that the computed distances match the outputs of a reference implementation such as Dijkstra. Without a correctness check, the reported speedups could in principle come from an algorithm that sometimes returns incorrect distances.

minor comments (3)

[Throughout] The manuscript has many typos and grammatical errors, such as 'childeren' instead of 'children', 'algorithm' missing a period, and inconsistent spacing; a careful proofreading is needed before resubmission.
[§3.3] Figure 3.3, which illustrates the waiting configuration and the distances used in the proof, is referenced but not included in the text, making the argument harder to follow.
[Abstract and references] The abstract begins by referring to a previous submission, which is an unusual style for a self-contained paper, and several references cite Wikipedia entries without full bibliographic details.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: PSTw is measured against independent baselines and its pruning premise is a standard shortest-path property, not an input that assumes the weighted result.

full rationale

The paper's central claims are (i) a new weighted all-pairs shortest-path algorithm PSTw based on pruning by shortest-path trees of adjacent vertices, (ii) a deadlock-freeness theorem, and (iii) empirical CPU-time and alpha comparisons against Dijkstra and Peng. None of these reduce by construction to an input. The pruning step uses the standard optimal-substructure fact that if a shortest path from v to x passes through adjacent w, the suffix is a shortest path from w to x, so only tree edges are needed; this fact is not equivalent to the claimed speedups or correctness of PSTw. The theorem in Sec. 3.3 is a proof attempt of deadlock-freeness, not a prediction derived from fitted parameters. Even if the theorem's inequality is questionable, that is a correctness gap, not circularity. The only self-citation, [Yamane19], is the source of the PSTu idea and of comparative remarks about alpha values; it is not invoked as a uniqueness theorem or as external proof of PSTw's correctness. The experiments use independent algorithms (Dijkstra and Peng) as baselines and no fitted parameter in PSTw is chosen to force the reported CPU time or alpha. Therefore no circular step is present.

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

The PSTw algorithm introduces no fitted numerical parameters and no new postulated entities. The experimental graph sizes and generator settings (n'=2 and n'=sqrt(n)) are evaluation choices, not fitted constants in the algorithm itself.

assumptions (4)

domain assumption All edge weights are positive.
Stated before the Theorem in §3.3; needed for the contradiction that a sum of positive edge weights is <= 0, and for Dijkstra-style shortest path reasoning.
standard math The suffix of any shortest v-to-x path through adjacent w is a shortest w-to-x path and is contained in T(w).
Used in §3.1 to justify pruning by T(w); it is true for positive weights but is never explicitly proved in the paper.
ad hoc to paper A t-vertex w''.is_determined = true implies its children in T(w) are complete and final.
Used in the else branch of extend() in §3.2 to traverse w''.children without waiting; this invariant is not proven.
ad hoc to paper Queue ordering in the deadlock proof implies the path length through v_{i+2} is no larger than the distance to x_{i+1}.
This is the key step of the Theorem in §3.3; it is asserted but not derived from the properties of a Dijkstra priority queue.

how reviews work

0 comments

Cite this review

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

@misc{pith2026190806798,
  author       = {Pith},
  title        = {Pith review of: A New Fast Weighted All-pairs Shortest Path Search Algorithm Based on Pruning by Shortest Path Trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LAU5RG6E}},
  note         = {Machine review of arXiv:1908.06798}
}

read the original abstract

Recently we submitted a paper, whose title is A New Fast Unweighted All-pairs Shortest Path Search Algorithm Based on Pruning by Shortest Path Trees, to arXiv. This is related to unweighted graphs. This paper also presents a new fast all-pairs shortest path algorithm for weighted graph based on the same idea. In Dijkstra algorithm which is said to be fast in weighted 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 in the same manner as the algorithm for unweighted graphs, and reduce {\alpha} drastically in comparison with Dijkstra algorithm. 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 short path trees is small. In case of weighted graphs, a problem which does not occur in unweighted graphs occurs. It is waiting for the generation of the shortest path tree of an adjacent vertex. Therefore, it is possible that a deadlock occurs. We prove our algorithm is deadlock-free. We compared our algorithm with Dijkstra and Peng algorithms. On Dijkstra algorithm ours outperforms it on speed and {\alpha} except that Dijkstra algorithm slightly outperforms ours or they are almost the same on CPU time in sparse scale-free graphs. The result on Peng algorithm is as follows: In speed and {\alpha}, ours outperforms Peng algorithm in hypercube-shaped and dense scale-free graphs, but conversely Peng algorithm outperforms ours in sparse scale-free graphs.

Figures

Figures reproduced from arXiv: 1908.06798 by the authors.

**Figure 3.** Fig3 [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

**Figure 3.** Fig.3 [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: and Table 4.1 show the comparison of CPU time of the two algorithms in hypercube [PITH_FULL_IMAGE:figures/full_fig_p013_4.png]

**Figure 4.** Figure 4: Fig.4.4 and Table 4.4 shows the comparison in [PITH_FULL_IMAGE:figures/full_fig_p014_4.png]

**Figure 4.** Figure 4: Fig.4.5 and Table 4.5 shows the comparison of CPU time. When [PITH_FULL_IMAGE:figures/full_fig_p015_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

1 extracted references · 1 canonical work pages

[1]

Breadth-first search

[BFS] Wikipedia’s title: “Breadth-first search” 18 [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.

[1] [1]

Breadth-first search

[BFS] Wikipedia’s title: “Breadth-first search” 18 [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