This section describes the All Pairs Shortest Path algorithm in the Neo4j Labs Graph Algorithms library.

This is documentation for the Graph Algorithms Library, which has been deprecated by the Graph Data Science Library (GDS). |

The All Pairs Shortest Path (APSP) calculates the shortest (weighted) path between all pairs of nodes. This algorithm has optimisations that make it quicker than calling the Single Source Shortest Path algorithm for every pair of nodes in the graph.

The All Pairs Shortest Path algorithm was developed by the Neo4j Labs team and is not officially supported. |

This section includes:

Some pairs of nodes might not be reachable between each other, so no shortest path exists between these pairs.
In this scenario, the algorithm will return `Infinity`

value as a result between these pairs of nodes.

Plain cypher does not support filtering `Infinity`

values, so `algo.isFinite`

function was added to help filter `Infinity`

values from results.

- The All Pairs Shortest Path algorithm is used in urban service system problems, such as the location of urban facilities or the distribution or delivery of goods. One example of this is determining the traffic load expected on different segments of a transportation grid. For more information, see Urban Operations Research.
- All pairs shortest path is used as part of the REWIRE data center design algorithm that finds a network with maximum bandwidth and minimal latency. There are more details about this approach in "REWIRE: An Optimization-based Framework for Data Center Network Design"

The following will create a sample graph:

```
MERGE (a:Loc {name:'A'})
MERGE (b:Loc {name:'B'})
MERGE (c:Loc {name:'C'})
MERGE (d:Loc {name:'D'})
MERGE (e:Loc {name:'E'})
MERGE (f:Loc {name:'F'})
MERGE (a)-[:ROAD {cost:50}]->(b)
MERGE (a)-[:ROAD {cost:50}]->(c)
MERGE (a)-[:ROAD {cost:100}]->(d)
MERGE (b)-[:ROAD {cost:40}]->(d)
MERGE (c)-[:ROAD {cost:40}]->(d)
MERGE (c)-[:ROAD {cost:80}]->(e)
MERGE (d)-[:ROAD {cost:30}]->(e)
MERGE (d)-[:ROAD {cost:80}]->(f)
MERGE (e)-[:ROAD {cost:40}]->(f);
```

The following will run the algorithm and stream results:

```
CALL algo.allShortestPaths.stream('cost',{nodeQuery:'Loc',defaultValue:1.0})
YIELD sourceNodeId, targetNodeId, distance
WITH sourceNodeId, targetNodeId, distance
WHERE algo.isFinite(distance) = true
MATCH (source:Loc) WHERE id(source) = sourceNodeId
MATCH (target:Loc) WHERE id(target) = targetNodeId
WITH source, target, distance WHERE source <> target
RETURN source.name AS source, target.name AS target, distance
ORDER BY distance DESC
LIMIT 10
```

Source | Target | Cost |
---|---|---|

A |
F |
100 |

C |
F |
90 |

B |
F |
90 |

A |
E |
80 |

C |
E |
70 |

B |
E |
80 |

A |
B |
50 |

D |
F |
50 |

A |
C |
50 |

A |
D |
50 |

This query returned the top 10 pairs of nodes that are the furthest away from each other. F and E appear to be quite distant from the others.

For now, only single-source shortest path support loading the relationship as undirected, but we can use Cypher loading to help us solve this. Undirected graph can be represented as Bidirected graph, which is a directed graph in which the reverse of every relationship is also a relationship.

We do not have to save this reversed relationship, we can project it using **Cypher loading**.
Note that relationship query does not specify direction of the relationship.
This is applicable to all other algorithms that use Cypher loading.

The following will run the algorithm, treating the graph as undirected:

```
CALL algo.allShortestPaths.stream('cost', {
nodeQuery:'MATCH (n:Loc) RETURN id(n) as id',
relationshipQuery:'MATCH (n:Loc)-[r]-(p:Loc) RETURN id(n) as source, id(p) as target, r.cost as weight',
graph:'cypher', defaultValue:1.0})
```

The default label and relationship-type projection has a limitation of 2 billion nodes and 2 billion relationships. Therefore, if our projected graph contains more than 2 billion nodes or relationships, we will need to use huge graph projection.

Set `graph:'huge'`

in the config:

```
CALL algo.allShortestPaths.stream('cost',{nodeQuery:'Loc',defaultValue:1.0,graph:'huge'})
YIELD sourceNodeId, targetNodeId, distance
RETURN sourceNodeId, targetNodeId, distance LIMIT 10
```

`algo.allShortestPaths.stream`

- Find shortest paths between all pairs of nodes.
- Returns a stream of source-target node to distance tuples for each pair of nodes.
- Writeback is not supported.
- If initialized with an non-existing weight-property, it will treat the graph as unweighted.