cancel
Showing results for 
Search instead for 
Did you mean: 

How to ignore the directions in dijkstra's algorithm

jaini_kiran
Node Clone

The code I used to create the graph is as below.

CREATE (a:Location {name: 'A'}),
       (b:Location {name: 'B'}),
       (c:Location {name: 'C'}),
       (d:Location {name: 'D'}),
       (e:Location {name: 'E'}),
       (f:Location {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);

And the graph is as below.


Actually I want to create bidirectional relationships. since it is not possible, I have created like this.
To find the shortest path between "A" node and "F" node using dijkstra's algorithm, I used the following code.

CALL gds.graph.create(
    'myGraph',
    'Location',
    'ROAD',
    {
        relationshipProperties: 'cost'
    }
)

MATCH (source:Location {name: 'A'}), (target:Location {name: 'F'})
CALL gds.beta.shortestPath.dijkstra.stream('myGraph', {
    sourceNode: id(source),
    targetNode: id(target),
    relationshipWeightProperty: 'cost'
})
YIELD index, sourceNode, targetNode, totalCost, nodeIds, costs
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
ORDER BY index

Output is as below.

This is fine. But when i tried to find the shortest path between "F" to "A" by using same code just by reversing the source and target nodes

MATCH (source:Location {name: 'F'}), (target:Location {name: 'A'})
CALL gds.beta.shortestPath.dijkstra.stream('myGraph', {
    sourceNode: id(source),
    targetNode: id(target),
    relationshipWeightProperty: 'cost'
})
YIELD index, sourceNode, targetNode, totalCost, nodeIds, costs
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
ORDER BY index

Output is as below

I think the reason is because there is no directed relation ships from "F" to "A".
I want to ignore the directions of relationships while calculating the dijkstra's shortest path.
Please tell me how can i ignore the directions of relationships in dijkstra's algorithm.
If this is not the reason, please tell me the code to find dijksra's shortest path between "F" to "A".
Thanks in advance.

1 ACCEPTED SOLUTION

If you want to reverse the direction of your relationships you'll need to use the orientation configuration option when you load your data, not just swap source/target in the algo call:

CALL gds.graph.create(
    'myGraph',
    'Location',
    'ROAD',
    {
        relationshipProperties: 'cost',
        orientation:'REVERSE'
    }
)

you can also set orientation:'UNDIRECTED' to load a graph without directed edges (inmemory, we duplicate the edges).

View solution in original post

1 REPLY 1

If you want to reverse the direction of your relationships you'll need to use the orientation configuration option when you load your data, not just swap source/target in the algo call:

CALL gds.graph.create(
    'myGraph',
    'Location',
    'ROAD',
    {
        relationshipProperties: 'cost',
        orientation:'REVERSE'
    }
)

you can also set orientation:'UNDIRECTED' to load a graph without directed edges (inmemory, we duplicate the edges).