All-Pairs Shortest Path (APSP)

Overview

The All-Pairs Shortest Path (APSP) algorithm computes the shortest path distance between every pair of reachable nodes in the graph. Unlike single-source algorithms (e.g., Delta-Stepping, SPFA) that compute distances from one source, APSP computes distances between all pairs simultaneously.

Concepts

All-Pairs Shortest Path

For a graph with N nodes, there are up to N×(N-1) directed pairs or N×(N-1)/2 undirected pairs. APSP computes the shortest path distance for each reachable pair. Unreachable pairs (in disconnected graphs) are excluded from results.

This implementation runs parallel BFS from every node to compute all pairwise distances. It is best suited for small to medium graphs due to the O(V²+VE) computational cost.

Example Graph

GQL
INSERT (A:default {_id: "A"}), (B:default {_id: "B"}),
       (C:default {_id: "C"}), (D:default {_id: "D"}),
       (E:default {_id: "E"}), (F:default {_id: "F"}),
       (G:default {_id: "G"}),
       (A)-[:default {value: 2}]->(B), (A)-[:default {value: 4}]->(F),
       (B)-[:default {value: 3}]->(C), (B)-[:default {value: 3}]->(D),
       (B)-[:default {value: 6}]->(F), (D)-[:default {value: 2}]->(E),
       (D)-[:default {value: 2}]->(F), (E)-[:default {value: 3}]->(G),
       (F)-[:default {value: 1}]->(E)

Parameters

Run Mode

Returns:

GQL
CALL algo.apsp({weight: "value"}) YIELD source, target, distance

Result:

Stream Mode

Returns the same columns as run mode, streamed for memory efficiency.

GQL
CALL algo.apsp.stream({weight: "value"}) YIELD source, target, distance
FILTER source = "A"
RETURN source, target, distance

Result:

Stats Mode

Returns:

GQL
CALL algo.apsp.stats({weight: "value"}) YIELD pairCount, maxDistance

Result: