18.13. Built-in Graph Algorithms

18.13.1. Find all shortest paths
18.13.2. Find one of the shortest paths between nodes
18.13.3. Execute a Dijkstra algorithm with similar weights on relationships
18.13.4. Execute a Dijkstra algorithm with weights on relationships

Neo4j comes with a number of built-in graph algorithms. They are performed from a start node. The traversal is controlled by the URI and the body sent with the request.

algorithm

The algorithm to choose. If not set, default is shortestPath. algorithm can have one of these values:

  • shortestPath
  • allSimplePaths
  • allPaths
  • dijkstra (optional with cost_property and default_cost parameters)
max_depth
The maximum depth as an integer for the algorithms like ShortestPath, where applicable. Default is 1.

18.13.1. Find all shortest paths

The shortestPath algorithm can find multiple paths between the same nodes, like in this example.

Figure 18.64. Final Graph


Example request

  • POST http://localhost:7474/db/data/node/243/paths
  • Accept: application/json
  • Content-Type: application/json
{
  "to" : "http://localhost:7474/db/data/node/238",
  "max_depth" : 3,
  "relationships" : {
    "type" : "to",
    "direction" : "out"
  },
  "algorithm" : "shortestPath"
}

Example response

  • 200: OK
  • Content-Type: application/json
[ {
  "start" : "http://localhost:7474/db/data/node/243",
  "nodes" : [ "http://localhost:7474/db/data/node/243", "http://localhost:7474/db/data/node/239", "http://localhost:7474/db/data/node/238" ],
  "length" : 2,
  "relationships" : [ "http://localhost:7474/db/data/relationship/125", "http://localhost:7474/db/data/relationship/131" ],
  "end" : "http://localhost:7474/db/data/node/238"
}, {
  "start" : "http://localhost:7474/db/data/node/243",
  "nodes" : [ "http://localhost:7474/db/data/node/243", "http://localhost:7474/db/data/node/242", "http://localhost:7474/db/data/node/238" ],
  "length" : 2,
  "relationships" : [ "http://localhost:7474/db/data/relationship/124", "http://localhost:7474/db/data/relationship/133" ],
  "end" : "http://localhost:7474/db/data/node/238"
} ]

18.13.2. Find one of the shortest paths between nodes

If no path algorithm is specified, a ShortestPath algorithm with a max depth of 1 will be chosen. In this example, the max_depth is set to 3 in order to find the shortest path between 3 linked nodes.

Figure 18.65. Final Graph


Example request

  • POST http://localhost:7474/db/data/node/250/path
  • Accept: application/json
  • Content-Type: application/json
{
  "to" : "http://localhost:7474/db/data/node/245",
  "max_depth" : 3,
  "relationships" : {
    "type" : "to",
    "direction" : "out"
  },
  "algorithm" : "shortestPath"
}

Example response

  • 200: OK
  • Content-Type: application/json
{
  "start" : "http://localhost:7474/db/data/node/250",
  "nodes" : [ "http://localhost:7474/db/data/node/250", "http://localhost:7474/db/data/node/246", "http://localhost:7474/db/data/node/245" ],
  "length" : 2,
  "relationships" : [ "http://localhost:7474/db/data/relationship/135", "http://localhost:7474/db/data/relationship/141" ],
  "end" : "http://localhost:7474/db/data/node/245"
}

18.13.3. Execute a Dijkstra algorithm with similar weights on relationships

Figure 18.66. Final Graph


Example request

  • POST http://localhost:7474/db/data/node/265/path
  • Accept: application/json
  • Content-Type: application/json
{
  "to" : "http://localhost:7474/db/data/node/268",
  "cost_property" : "cost",
  "relationships" : {
    "type" : "to",
    "direction" : "out"
  },
  "algorithm" : "dijkstra"
}

Example response

  • 200: OK
  • Content-Type: application/json
{
  "weight" : 2.0,
  "start" : "http://localhost:7474/db/data/node/265",
  "nodes" : [ "http://localhost:7474/db/data/node/265", "http://localhost:7474/db/data/node/266", "http://localhost:7474/db/data/node/268" ],
  "length" : 2,
  "relationships" : [ "http://localhost:7474/db/data/relationship/157", "http://localhost:7474/db/data/relationship/158" ],
  "end" : "http://localhost:7474/db/data/node/268"
}

18.13.4. Execute a Dijkstra algorithm with weights on relationships

Figure 18.67. Final Graph


Example request

  • POST http://localhost:7474/db/data/node/256/path
  • Accept: application/json
  • Content-Type: application/json
{
  "to" : "http://localhost:7474/db/data/node/259",
  "cost_property" : "cost",
  "relationships" : {
    "type" : "to",
    "direction" : "out"
  },
  "algorithm" : "dijkstra"
}

Example response

  • 200: OK
  • Content-Type: application/json
{
  "weight" : 6.0,
  "start" : "http://localhost:7474/db/data/node/256",
  "nodes" : [ "http://localhost:7474/db/data/node/256", "http://localhost:7474/db/data/node/257", "http://localhost:7474/db/data/node/254", "http://localhost:7474/db/data/node/255", "http://localhost:7474/db/data/node/252", "http://localhost:7474/db/data/node/253", "http://localhost:7474/db/data/node/259" ],
  "length" : 6,
  "relationships" : [ "http://localhost:7474/db/data/relationship/144", "http://localhost:7474/db/data/relationship/146", "http://localhost:7474/db/data/relationship/148", "http://localhost:7474/db/data/relationship/151", "http://localhost:7474/db/data/relationship/153", "http://localhost:7474/db/data/relationship/154" ],
  "end" : "http://localhost:7474/db/data/node/259"
}