Delta-Stepping SSSP

Overview

The single-source shortest path (SSSP) problem involves finding the shortest paths from a given source node to all other reachable nodes in a graph. In weighted graphs, the shortest path minimizes the total edge weights; in unweighted graphs, it minimizes the number of edges (hops). The cost or distance of a path refers to this total weight or count.

The Delta-Stepping algorithm is a parallelizable variant of Dijkstra's algorithm, designed to improve performance on large graphs by dividing work into manageable steps.

Related material of the algorithm:

• U. Meyer, P. Sanders, Δ-Stepping: A Parallel Single Source Shortest Path Algorithm (1998)

Concepts

Delta-Stepping Algorithm

The Delta-Stepping SSSP algorithm introduces the concept of buckets and performs distance updates in a more coarse-grained manner. The algorithm utilizes a positive real number parameter delta (Δ) to achieve the following:

• Maintain an array of buckets, such that bucket B[i] contains nodes whose distance falls within the range [iΔ, (i+1)Δ). The distance update also includes assigning the node to the corresponding bucket based on its updated distance value.
• Distinguish between light edges with weight ≤ Δ and heavy edges with weight > Δ. Light-edge nodes are prioritized during distance updates as they have lower weights and are more likely to yield shorter paths.

Below is an example to compute the weighted shortest paths in an undirected graph from source node b with Δ = 3:

1. Initialize the distance of the source node as 0 and the distances of other nodes as infinity. The source node is placed into bucket B[0].

2. Visit and remove all nodes from the first nonempty bucket B[i]:

• Update distances for all light-edge neighbors of the removed nodes, assign the updated nodes to B[i] or B[i+1].
• If B[i] is refilled, repeat the above until B[i] is empty.
• Update distances for all heavy-edge neighbors.

Remove b from B[0]: update light-edge neighbors dist(a) = min(0+2,∞) = 2 (assign to B[0]) and dist(d) = min(0+3,∞) = 3 (assign to B[1]), defer heavy-edge neighbor c
Remove a from refilled B[0]: no unvisited light-edge neighbors, defer heavy-edge neighbor d
B[0] is empty, update heavy-edge neighbors: dist(c) = min(0+5,∞) = 5 (assign to B[1]), dist(d) = min(2+4,3) = 3 (no update)

3. Repeat step 2 until all buckets are empty.

Remove d and c from B[1]: update unvisited light-edge neighbors dist(g) = min(5+2,∞) = 7 (assign to B[2]), defer heavy-edge neighbor e
B[1] is empty, update heavy-edge neighbors: dist(e) = min(5+4,∞) = 9 (assign to B[3])
Remove g from B[2]: no unvisited light-edge neighbors, defer heavy-edge neighbor f
B[2] is empty, update heavy-edge neighbors: dist(f) = min(7+5,∞) = 12 (assign to B[4])
Remove e from B[3]: update unvisited light-edge neighbor dist(f) = min(9+1,12) = 10 (assign to B[3]), no heavy-edge neighbors
Remove f from refilled B[3]: no unvisited light/heavy-edge neighbors

The algorithm ends here since all buckets are empty.

By dividing nodes into buckets and processing them in parallel, the Delta-Stepping algorithm efficiently leverages available computational resources, making it well-suited for large-scale graphs and parallel computing environments.

Considerations

• Delta-Stepping doesn't work with negative weights — it assumes once a node is visited, its distance is final. A negative-weight edge could later provide a shorter path, violating this assumption.
• In disconnected graphs, the algorithm only computes shortest paths to nodes within the same connected component as the source node.

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.deltastepping({
  startNode: "A"
}) YIELD nodeId, distance

Stream Mode

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

GQL
CALL algo.deltastepping.stream({
  startNode: "A"
}) YIELD nodeId, distance
RETURN nodeId, distance

Stats Mode

Returns:

GQL
CALL algo.deltastepping.stats({
  startNode: "A"
}) YIELD nodesReached, maxDistance