Implement Dijkstra Algorithm using cypher query in apache age

Question

I have a graph named "CITIES" which contains vertices which are cities themselves and edges between those cities and there is one property on those edges which is the distance between the edges. I want to find shortest path between any 2 cities using the Dijkstra algorithm. How would I use cypher query language to do that. I am using apache age extension.

Answer 1

There isn't a direct approach to that. Because Dijkstra Algorithm requires a lot steps to follow and the steps changes depending on how you store the node and edges. But There is one way that you can do this in your project. There are drivers in the repo where you can connect age in some programming language. After connecting the database make query for nodes and edges and then write your own dijstkra algorithm for the shortest path.

Answer 2

There is not yet an in built AGE method to find the shortest path between two vertices in any algorithm be it Dijkstra, Floyd Warshall, Bellman Ford or any other. But as you can query the vertices and edges using cypher queries. You can write Postgres functions to follow a particular algorithm and find out the shortest distance.
You can also refer the article for Postgres functions:
https://www.postgresqltutorial.com/postgresql-plpgsql/postgresql-create-function/

Answer 3

According to Wikipedia's article on Dijkstra's algorithm: "Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks. [...] For a given source node in the graph, the algorithm finds the shortest path between that node and every other.  It can also be used for finding the shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined."

There is no function in AGE that calculates the shortest path from one vertex to another, but we can create a query for it. Considering that each edge in the graph has a property that contains the cost to go from one vertex to another (let's name it travelTime), and that each vertex has a name property, you can execute the following query to return the cost from one vertex to another:

SELECT * FROM cypher('Cities', $$

    MATCH paths = (a:City {name: 'Seattle'})-[:HAS_ROUTE*]-(b:City {name: 'Bellevue'})

    WITH paths, relationships(paths) AS rels

    UNWIND rels AS rel

    WITH nodes(paths) AS nodes,
        collect(rel.travelTime) AS routes,
        sum(rel.travelTime) AS travelTime

    RETURN nodes, routes, travelTime

$$) AS (cities agtype, routes agtype, travelTime agtype)

ORDER BY travelTime;

Here, it is going to traverse the graph and find all possible routes from Seattle to Bellevue. Once the connections have been processed, the query will extract the nodes, a list of the times for each relationship, and the sum of travel times for each path.