In the previous post, a brief description about running Lua script on Redis and a code snippet to add a graph edge to a hash are given. In this post, an implementation of the Dijkstra’s shortest path algorithm is explained. I will not explain the algorithm itself since there are already so many articles explaining about it, e.g., Wikipedia’s page. Priority Queue A priority queue plays a primary role on the Dijkstra’s algorithm.
Redis provides several kind of data structures and many functions to manipulate those data. But sometimes additional function is required for satisfying some demand. The power of Lua For example, you may need to delete a string only when the string is equal to a specified one but there is no such function. Although this is easy to implement by checking the equality of GET-ed string in client-side program and executing DEL command if necessary, it is difficult to make sure that this operation is atomic and you also have to implement a remote locking mechanism.