Redis Dijkstra ShortestPath

Implementations of Dijkstra algorithm on RedisGraph. There are two assumptions for a database:

  1. Each node should contain id property with unique id.
  2. Each relation should contain w property with non-negative numeric value that represents cost of transitioning from source node to destination node.


Here's the whole story:

Inspiration

One of the most important problems in classical graph theory is finding the shortest path between two nodes in a weighted oriented graph. Since RedisGraph represents an oriented graph with an option of making it weighted by adding an attribute to relation, such functionality may be required quite frequently. We noticed several unresolved issues and StackOverflow questions about this. Finding the shortest path is an important problem in a variety of subjects, which includes, but is not limited, to cartography, trip planning, flight search, etc. Graph databases are natural solutions for storing such data. Having this feature for Redis will make it more attractive for companies that cover such business areas.

What it does

Our script has two main use cases.

Finding quickest path and its cost from a source node to a specified destination node
Use case example:
Cheapest flight (with transitions) from city A to city B. One can also account for a time by creating a combined cost of time and ticket price. The fastest route between two places via several roads (some on them might be one-way). Solving undetermined abstract machine case - e.g. by representing Rubik's cube states as a graph one might find the quickest solution.

Finding minimal cost for each node from specified source node
Use case example:
For services that offer tours a table of a minimal price for each destination can be shown to the user. E.g. tour aggregators may show a list of available destinations together with minimal prices.

This can be extended with an additional function that takes precomputed costs as input. This will allow to computationally quickly process user request for a path for selected destination after user will see the table of available destinations and prices.

How we built it

We have created a Python script that is calling RedisGraph queries and processing the results. Since Python is a popular programming language, such functions can be easily in-built into a variety of applications.

Challenges we ran into

We need to make assumptions about the way how relations and nodes hold the information. In this case, we had to make two assumptions:

  1. Each node should contain id property with a unique id.
  2. Each relation should contain w property with a non-negative numeric value that represents the cost of transitioning from source node to destination node.
    It should be noted, however, that form of such assumptions can be easily changed (e.g. the name of the property can be easily edited in the script or script can be tweaked to allow it to be passed as a parameter).

Accomplishments that we're proud of

The script can be applied to a variety of problems and businesses. travel aggregators, map services, social networking services, etc.

What we learned

We have deepened and polished our skills with RedisGraph.

What's next for Redis Dijkstra ShortestPath

The algorithm can be extended in a way to allow a user to specify the type of relation to take into account. Additionally, it is possible to allow a user to pass a discounting factor for each relationship type - e.g. if we would take an example of finding the shortest route on a map, we can either define a cost of a ride as something like 0.6 money + 0.8 * time, or specify that car rides are 1.0 * time, while ferry rides are 1.5 * time since it will make a user use a different type of transportation. Additionally, it is possible to change cost based on the number of transitions - e.g. if we take classical "find cheapest flight from city A to city B with transits" problem, one might want to take a number of transits into account, since having five consequent flights might be worse for a user than paying slightly more for two flights.



Technical part:

Python file contains three functions:

find_path

Returns path and cost to get from source node to destination node.

Arguments:

  • db_name: name of database on which search will be done.
  • source_node_id: id of node from which path should be started.
  • destination node id: id of node on which path should end.

Returns:
Tuple (path, cost), where

  • path is a list of found path with minimal cost (starts from source_node_id and ends with destination_node_id).
  • cost is float that is a cost of a path.

Use case example:

  • Cheapest flight (with transitions) from city A to city B. One can also account for a time by creating a combined cost of time and ticket price.
  • The fastest route between two places via several roads (some on them might be one-way).
  • Solving undetermined abstract machine case - e.g. by representing Rubik's cube states as a graph one might find the quickest solution.

find_all_costs

Returns costs to get from source node to any node.

Arguments:
db_name: name of database on which search will be done. source_node_id: id of node from which path should be started.

Returns:
Dictionary with node id: cost to node with node_id from source node.

Use case example:

  • For services that offer tours a table of a minimal price for each destination can be shown to the user. E.g. tour aggregators may show a list of available destinations together with minimal prices.

Returns path from source node to destination node with smallest total cost for a precomputed costs (such as find_all_costs returns).

Arguments:

  • db_name: name of database on which search will be done.
  • source_node_id: id of node from which path should be started.
  • destination node id: id of node on which path should end.
  • costs: precomputed with find_all_costs costs of reaching each node in form of a dictionary with pairs {id: cost} for each node.

Returns:

  • path - a list of found path with minimal cost (starts from source_node_id and ends with destination_node_id).

Use cases:

Similar use cases as for find_path, but this function will allow user to firstly run find_all_costs, analyse costs and after that select destination node and find path to desired destination.

Built With

Share this project:

Updates