Dijkstra’s Algorithm in Ruby

First, let’s understand what is Dijkstra’s algorithm. It is an algorithm to find the shortest path between nodes in a graph. Which may represent, for example, road networks. This algorithm created by computer scientist Edsger W. Dijkstra.

The algorithm works with a set S of shortest paths, starting with an initial vertex I. The algorithm searches the vertices belonging to S for the vertex with the smallest distance relative to I and adds it to S. Repeating until all vertices achievable by I are in S.

Algorithm

The first definition of the initial node. We have to know or the shortest path from the initial node to the Y node. Dijkstra’s algorithm assigns some initial distance values and tries to improve them step by step.

1. Assign the zero and infinite starting node to all other nodes. Set the starting node to current.
2. For the current node, consider all your unvisited neighbors and calculate your tentative distances through the current node. Compare the recently calculated temporary distance with the current assigned value and assign the shortest.
3. When we finished considering all unvisited neighbors for the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be scanned again.
4. If the destination node has marked as visited or if the shortest tentative distance between the nodes in the unvisited set is infinite stops, the algorithm has ended.
5. Otherwise, select the unvisited node marked with the shortest temporary distance, configure it as the new “current node” and go back to step 3.

Pseudocode

This pseudocode inspired by Wikipedia

Let us understand with an example

The smallest path from vertex 0 to vertex 4.

Code

Finally, let’s see the ruby code.

Examples of inputs:

Then that’s it !!! I hope you understand!

Please write comments if you find anything incorrect.