Johnson's Algorithm
Introduction
Johnson's algorithm finds the shortest path between every pair of nodes in the loaded graph. It takes no source or target, and returns one path for each ordered pair of nodes where a path exists.
The number of paths grows with the square of the number of nodes: a graph with N connected nodes can return close to N × N paths. Use it only on small graphs, or limit the loaded graph with vertices(...), edges(...) and excludeVertexIds(...). To find paths from a few sources on a large graph, run Dijkstra's algorithm once per source instead, or Bellman-Ford if weights can be negative. See Sizing for large graphs.
The program follows edges in their stored direction only. Edge weights can be negative (PuppyGraph 1.20.0 and later). If the loaded graph contains a negative-weight cycle, the run fails and the error names the nodes on the cycle and its total weight. Paths that can pass through the cycle have no shortest length, so Johnson's algorithm returns no paths for that graph until the cycle is removed or left out. Unlike Bellman-Ford, which fails only on a negative-weight cycle that its source can reach, Johnson's algorithm fails on such a cycle anywhere in the loaded graph. To leave a cycle out, narrow the loaded graph with the common arguments that select labels or exclude nodes and edges.
Version requirement
Negative edge weights in Johnson's algorithm are available in PuppyGraph 1.20.0 and later. In earlier versions, LocalJohnsonShortestPathsProgram needs edge weights of zero or more and fails on a negative weight. For negative weights on an earlier version, run Bellman-Ford from each source.
Run Johnson's algorithm from Cypher with CALL algo.shortestpath.johnson, or from Gremlin with LocalJohnsonShortestPathsProgram. See Shortest Paths for how to run it, the output fields and the arguments shared by all shortest path algorithms.
Query Example
The shortest path between every connected pair of nodes in the Modern example graph:
CALL algo.shortestpath.johnson({
labels: ['person', 'software'],
relationshipTypes: ['knows', 'created'],
relationshipWeightProperty: 'weight'
}) YIELD vertexList, edgeList, weight
RETURN vertexList, edgeList, weight
ORDER BY weight
Output:
[
{
"vertexList": ["person[v6]", "software[v3]"],
"edgeList": ["created[e12]"],
"weight": 0.2
},
{
"vertexList": ["person[v1]", "software[v3]"],
"edgeList": ["created[e9]"],
"weight": 0.4
},
{
"vertexList": ["person[v4]", "software[v3]"],
"edgeList": ["created[e11]"],
"weight": 0.4
},
{
"vertexList": ["person[v1]", "person[v2]"],
"edgeList": ["knows[e7]"],
"weight": 0.5
},
{
"vertexList": ["person[v1]", "person[v4]"],
"edgeList": ["knows[e8]"],
"weight": 1.0
},
{
"vertexList": ["person[v4]", "software[v5]"],
"edgeList": ["created[e10]"],
"weight": 1.0
},
{
"vertexList": ["person[v1]", "person[v4]", "software[v5]"],
"edgeList": ["knows[e8]", "created[e10]"],
"weight": 2.0
}
]
graph.program(
LocalJohnsonShortestPathsProgram.build()
.vertices("person", "software")
.edges("knows", "created")
.weightProperty("weight")
.create()
).submitAndGetLocal().getMapResult()
The graph has 6 nodes, but its edges lead only away from marko, josh and peter, so 7 pairs are connected:
[
{
"vertexList": ["person[v4]", "software[v5]"],
"edgeList": ["created[e10]"],
"edgeResultList": [{"id": "created[e10]", "from": "person[v4]", "to": "software[v5]"}],
"weight": 1.0
},
{
"vertexList": ["person[v4]", "software[v3]"],
"edgeList": ["created[e11]"],
"edgeResultList": [{"id": "created[e11]", "from": "person[v4]", "to": "software[v3]"}],
"weight": 0.4
},
{
"vertexList": ["person[v6]", "software[v3]"],
"edgeList": ["created[e12]"],
"edgeResultList": [{"id": "created[e12]", "from": "person[v6]", "to": "software[v3]"}],
"weight": 0.2
},
{
"vertexList": ["person[v1]", "person[v4]"],
"edgeList": ["knows[e8]"],
"edgeResultList": [{"id": "knows[e8]", "from": "person[v1]", "to": "person[v4]"}],
"weight": 1.0
},
{
"vertexList": ["person[v1]", "person[v2]"],
"edgeList": ["knows[e7]"],
"edgeResultList": [{"id": "knows[e7]", "from": "person[v1]", "to": "person[v2]"}],
"weight": 0.5
},
{
"vertexList": ["person[v1]", "person[v4]", "software[v5]"],
"edgeList": ["knows[e8]", "created[e10]"],
"edgeResultList": [
{"id": "knows[e8]", "from": "person[v1]", "to": "person[v4]"},
{"id": "created[e10]", "from": "person[v4]", "to": "software[v5]"}
],
"weight": 2.0
},
{
"vertexList": ["person[v1]", "software[v3]"],
"edgeList": ["created[e9]"],
"edgeResultList": [{"id": "created[e9]", "from": "person[v1]", "to": "software[v3]"}],
"weight": 0.4
}
]
Parameters
| Cypher argument | Gremlin method | Description | Required | Default Value |
|---|---|---|---|---|
relationshipWeightProperty |
weightProperty(String name) |
The edge property to use as the weight | Yes |
The common arguments also apply.