1.8 Shortest path

Attention! This algorithm is proposed in its alpha version in the Neo4J Data Science Library.

The Shortest Path algorithm calculates the shortest (weighted) path between a pair of nodes. In this category, Dijkstra’s algorithm is the most well known. It is a real time graph algorithm, and can be used as part of the normal user flow in a web or mobile application.

When to use the Shortest Path algorithm

• Finding directions between physical locations. This is the most common usage, and web mapping tools such as Google Maps use the shortest path algorithm, or a variant of it, to provide driving directions.
• Social networks can use the algorithm to find the degrees of separation between people. For example, when you view someone’s profile on LinkedIn, it will indicate how many people separate you in the connections graph, as well as listing your mutual connections.

Dijkstra does not support negative weights. The algorithm assumes that adding a relationship to a path can never make a path shorter - an invariant that would be violated with negative weights.

1.8.1 Syntax

1.8.1.1 Write

The following will run the algorithm and write back results:

CALL gds.alpha.shortestPath.write(configuration: Map)
YIELD
  // general write return columns
  nodeCount: Integer,
  totalCost: Float

Parameters

General configuration of the algorithm execution on an anonymous graph

Algorithm specific configuration

Results

1.8.1.2 Stream

The following will run the algorithm and stream results:

CALL gds.alpha.shortestPath.stream(configuration: Map)
YIELD
  // general write return columns
  nodeId: Integer,
  cost: Float

Parameters

General configuration of the algorithm execution on an anonymous graph

Algorithm specific configuration

Results

1.8.2 Example

The following will create a sample graph:

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

Dijkstra Shortest Path

The following will run the algorithm and stream results:

MATCH (start:Loc {name: 'A'}), (end:Loc {name: 'F'})
CALL gds.alpha.shortestPath.stream({
  nodeProjection: 'Loc',
  relationshipProjection: {
    ROAD: {
      type: 'ROAD',
      properties: 'cost',
      orientation: 'UNDIRECTED'
    }
  },
  startNode: start,
  endNode: end,
  relationshipWeightProperty: 'cost'
})
YIELD nodeId, cost
RETURN gds.util.asNode(nodeId).name AS name, cost

Results

The quickest route takes us from A to F, via C, D, and E, at a total cost of 160:

• First, we go from A to C, at a cost of 50.

• Then, we go from C to D, for an additional 40.

• Then, from D to E, for an additional 30.

• Finally, from E to F, for a further 40.

  The following will run the algorithm and write back results:

  MATCH (start:Loc {name: 'A'}), (end:Loc {name: 'F'})
  CALL gds.alpha.shortestPath.write({
    nodeProjection: 'Loc',
    relationshipProjection: {
      ROAD: {
        type: 'ROAD',
        properties: 'cost',
        orientation: 'UNDIRECTED'
      }
    },
    startNode: start,
    endNode: end,
    relationshipWeightProperty: 'cost',
    writeProperty: 'sssp'
  })
  YIELD nodeCount, totalCost
  RETURN nodeCount,totalCost
  

  Results

  nodeCount	totalCost
  5	160

Cypher projection

If node label and relationship type are not selective enough to create the graph projection to run the algorithm on, you can use Cypher queries to project your graph. This can also be used to run algorithms on a virtual graph.

Set graph:'cypher' in the config:

MATCH (start:Loc {name: 'A'}), (end:Loc {name: 'F'})
CALL gds.alpha.shortestPath.write({
  nodeQuery:'MATCH(n:Loc) WHERE NOT n.name = "c" RETURN id(n) AS id',
  relationshipQuery:'MATCH(n:Loc)-[r:ROAD]->(m:Loc) RETURN id(n) AS source, id(m) AS target, r.cost AS weight',
  startNode: start,
  endNode: end,
  relationshipWeightProperty: 'weight',
  writeProperty: 'sssp'
})
YIELD nodeCount, totalCost
RETURN nodeCount,totalCost