From A-Town to Z-Town: Find the shortest route through the alphabet

Neo4j Graph Platform Graph Algorithms/Graph Data Science
1

Hi there,

I am new to neo4j and would like to use it to answer the following question:
What is the shortest route in terms of distance in kilometres from "A-Town" to "Z-Town", where the tour should follow the alphabet using the first letters of the places crossed.

For this I have a dataset that contains the shortest routes between places followed by the first letter, i.e. routes between "A-Town" and all places starting with B, all routes from places with B to places with C, etc.

So with that I have created a graph that consists of

  • 9153 Place Nodes representing different places with a Id and a Name property

  • around 3.2 Mio PATH relationships between these nodes with a Distance property

I have tried the Dijkstra Shortest Path algorithm

MATCH (source:Place {Id: "1"}),
      (target:Place {Id:"9153"})

CALL gds.shortestPath.dijkstra.stream(
  'routes',
  {
    sourceNode:source,
    targetNode:target,
    relationshipWeightProperty:'Distance'
  })
YIELD index, sourceNode, targetNode, totalCost, nodeIds, costs, path
RETURN
    index,
    gds.util.asNode(sourceNode).Name AS sourceNodeName,
    gds.util.asNode(targetNode).Name AS targetNodeName,
    totalCost,
    [nodeId IN nodeIds | gds.util.asNode(nodeId).Name] AS nodeNames,
    costs,
    nodes(path) as path
ORDER BY index

and some other algorithms, but I always just get the Warning Information

This query builds a cartesian product between disconnected patterns.

The warning makes sense, of course, since extremely many comparisons have to be queried.

Therefore now my question: What is the best way to proceed here, is there a suitable solution for this at all?

I would be very happy about any suggestions and help!

2

Don’t worry about the warning. Your query pattern does result in a Cartesian product, but it is between two unique nodes, so no big deal.

Try the following instead. It will provide the same result, but maybe the warning will go away.

MATCH (source:Place {Id: "1"})
MATCh (target:Place {Id:"9153"})
1 Like
3

Thank you for your answer, with this the warning disappeared. At first I still got no output, just

(no changes, no records)

but the problem was that I had strings instead of integers as the Ids in the MATCH statement. So

MATCH (source:Place {Id: 1})
MATCH (target:Place {Id: 9153})

did the trick :-)

4

Good catch.

Just a note about something similar, when importing via 'load csv' all values are strings, so if you want to load an integer or float, you will need to convert the string from the csv file using toInteger() or toFloat(). Just a heads up, as this is gotten all of us the first time.