Interesting results using gds.shortestpath.astar

Hello Community!

Can anyone help me explain this? I'm working on a navigation project and returning routes using both Dijkstra and A*. Both calculations use practically identical queries - except for the addition of the latitude and longitude parameters for A*. Something strange seems to be happening with the A* calculation though, because the path being returned is definitely not the shortest :slight_smile:
The data has been taken from OpenStreetMap and added/appended for routing.
This is the Dijkstra result:

This is the A* result with the same start source and target:

And here's the call being used :

WHERE contains('<Name-of-destination>') 
MATCH (p:ParkingSpaceNode) 
WITH x,id(p) as pId, distance(x.location,p.location) as d 
    nodeProjection: '*',     
    longitudeProperty: 'lon', 
    latitudeProperty: 'lat',     
}) YIELD  nodeIds, totalCosts //include totalCosts for analysis
WITH [nodeId IN nodeIds | gds.util.asNode(nodeId).location] as coords
RETURN coords

A short explanation:

  1. I select a destination and derived the closest non-occupied parking space based on the "line-of-site" distance. (WITH... distance() ... LIMIT 1). This works fine.
  2. Calculate the path using A* or Dijkstra.
  3. The returned coordinates are then packaged in a GeoJSON and sent to a MapBox display.

The path calculation is undirected, and all relations (pathways) are "two-way"...
The example shown in the pictures calculate a 70m path with Dijkstra and 413m for A* :rofl:
Is anyone working with A* at the moment that could help explain what might be happening in the middle to divert the path so far out of the way?

Any ideas would be greatly appreciated!


before going any deeper, are you using directional relationships to represent directional streets? (and two rels if two way street?) at a glance it looks like Dijkstra is proposing going the wrong way up a one way street? but a* does seem to be taking the scenic tour (could it be cost or directional traffic?)

Hi Joel,
that's what I originally suspected, but I checked the relationships and everything seems to be undirected. Here's an example of a relationship for the area in question:

  "identity": 8881,
  "start": 699,
  "end": 696,
  "type": "ROUTE",
  "properties": {
"toRel": 3266,
"distance": 23.609465317591265,
"fromRel": 3268

You're right, technically they are one way streets ;) And there is, in most cases, only one relation But the relationships are not marked as such. Do you think that could make a difference? I assumed specifying "UNDIRECTED" in the call would have taken care of that.

So I just tried duplicating all the ROUTE relationships and changing the direction.. Still the same result :frowning:

I'm embarrassed to say, but I found the problem...
At some point when I was adding nodes to the graph, I somehow managed to swap the latitude and longitude values of certain nodes. :blush:
Because Dijkstra relies purely on the cost of the path and A* requires the haversine distance for the heuristic, it decided that a point somewhere in the middle of Yemen instead of Austria wasn't a suitable route..
Can't understand that myself... :rofl:

Anyway, problem solved. A tip for anyone with strange A* routes.. Check your coordinates!!!