cancel
Showing results for 
Search instead for 
Did you mean: 

Join the community at Nodes 2022, our free virtual event on November 16 - 17.

Shortest path algorithms in GDS lib do not work properly

2736484336
Node

hi ,
I use the Dijkstra Source-Target algorithm to find the weighted shortest path via the cypher code below.
However, the result still shows the unweighted shortest path even after I added the "relationshipWeightProperty" in my cypher "call" query. Please give some advise for how to get the weighted shortest path, thanks.
the link for data and code as below:

https://github.com/neo4j-graph-analytics/book/raw/master/data/transport-relationships.csv
https://github.com/neo4j-graph-analytics/book/raw/master/data/transport-nodes.csv

MATCH (source:Place {id:'Amsterdam'}),(target:Place {id:'London'})
CALL gds.shortestPath.dijkstra.stream({nodeProjection:'Place',relationshipProjection:'EROAD',relationshipProperties:'distance',sourceNode:source,targetNode:target,relationshipWeightProperty:'distance'})
YIELD nodeIds,costs
WITH [nodeId in nodeIds|gds.util.asNode(nodeId).id] AS nodeName,costs AS costs, size(nodeIds) AS siz
UNWIND range(0,siz-1) AS n
RETURN nodeName[n] AS city, costs[n] AS step
1 ACCEPTED SOLUTION

shiny
Node

I've read this book.
And for the latest version of Dijkstra Source-Target algorithm it's applied as directed.
So you'd configure to undirected first.

Here are 2 pieces of code to do that:

CALL gds.graph.create(
    'g1',
    'Place',
    { EROAD: {type: "EROAD", orientation: "UNDIRECTED"}},
    {
        relationshipProperties: 'distance'
    }
)

Then run the algorithm:

MATCH (source:Place {id: "Amsterdam"}), (destination:Place {id: "London"})
CALL gds.shortestPath.dijkstra.stream('g1',{
    sourceNode: source,
    targetNode: destination,
    relationshipWeightProperty: 'distance'
}) 
YIELD nodeIds, costs
WITH [nodeId in nodeIds|gds.util.asNode(nodeId).id] AS nodeName,costs AS costs, size(nodeIds) AS siz
UNWIND range(0,siz-1) AS n
RETURN nodeName[n] AS city, costs[n] AS step

That's it.

View solution in original post

2 REPLIES 2

2736484336
Node

path of result generated by code above is still "Amsterdam-Immingham-Doncaster-London" same as unweighted path. The weighted path should be "Amsterdam-Den Haag-Hoek van Holland-Felixstowe-Ipswich-Colchester-London". this example in the book is represented by algo lib but this lib is retired so I use the GDS lib to rewrite the example. It seems the GDS lib not work well

shiny
Node

I've read this book.
And for the latest version of Dijkstra Source-Target algorithm it's applied as directed.
So you'd configure to undirected first.

Here are 2 pieces of code to do that:

CALL gds.graph.create(
    'g1',
    'Place',
    { EROAD: {type: "EROAD", orientation: "UNDIRECTED"}},
    {
        relationshipProperties: 'distance'
    }
)

Then run the algorithm:

MATCH (source:Place {id: "Amsterdam"}), (destination:Place {id: "London"})
CALL gds.shortestPath.dijkstra.stream('g1',{
    sourceNode: source,
    targetNode: destination,
    relationshipWeightProperty: 'distance'
}) 
YIELD nodeIds, costs
WITH [nodeId in nodeIds|gds.util.asNode(nodeId).id] AS nodeName,costs AS costs, size(nodeIds) AS siz
UNWIND range(0,siz-1) AS n
RETURN nodeName[n] AS city, costs[n] AS step

That's it.