We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies.

We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies. Less

We use cookies and other tracking technologies... More

Login or register
to apply for this job!

Login or register to start contributing with an article!

Login or register
to see more jobs from this company!

Login or register
to boost this post!

Show some love to the author of this blog by giving their post some rocket fuel 🚀.

Login or register to search for your ideal job!

Login or register to start working on this issue!

Engineers who find a new job through Functional Works average a 15% increase in salary 🚀

Blog hero image

DIJKSTRA’S ALGORITHM

Carlos Hernandez Navarro 18 June, 2020 | 5 min read

DIJKSTRA’S ALGORITHM

INTRODUCTION

In this short article I am going to show why Dijkstra’s algorithm is important and how to implement it. If you need some background information on graphs and data structure I would recommend reading more about it in Geeks for Geeks before reading this article. In any case I will try to be as clear as possible.

Before we get into this tutorial I would like to show you what the final result of our Dijkstra’s application will be:

I decided to create a React application as I think that one of the best ways to learn a new concept is by seeing it in action.

WHY DIJKSTRA?

There are two reasons behind using Dijkstra’s algorithm. On one hand, it is a simple algorithm to implement. On the other hand one of the main features of this algorithm is that we only have to execute it once to calculate all the distances from one node in our graph and save it. This is a really important concept for future iterations where we will need to know what the shortest path from our init node is and we do not need to calculate it again, we can just use the previous calculated information, giving a really good performance.

For example, in the real world, we can use Dijkstra’s algorithm to calculate the distance between London and all the cities in the UK. Once this information is calculated and saved, we only have to read the previously calculated information. For example, looking at our data we can see what the shortest path from Norwich to London is. Later on in this article I will show you a real life example and how we can use previously calculated distances.

HOW IT WORKS

To explain how this algorithm works first I need to show you the graph that we are going to use in the rest of this section:

In the previous graph we can see 6 nodes from A-F, node A (highlighted green) is our start point and node F (highlighted orange) is our destination. Let’s now analyse this algorithm step by step:

  1. Initialise all the distances with the value infinite, except the initial node which is going to be initialized with the value 0.

Distance table:

  1. Add the current node, in this case ‘Node A’, into the visited array. We have to maintain this information to prevent analysing the same node more than once.

  1. Calculate the distance between the current node and its children, the formula to calculate this distance is: totaldistance = currentnodedistance + pathdistance, for example, between A and B the total_distant = 0 + 2 = 2. After this iteration the graph looks like this:

Distance table:

  1. Now, analyse the next node. This node will be the no visited node with the minimum distance, in our case this node will be ‘Node B’. In this step we are going to repeat steps 2 and 3:

Distance table:

Important: the distance is updated only if the new distance is lower than the previous one. In this step the distance from B to D is 2 + 11 > 9, in this case the value remains at 9 because it is lower than 13.

  1. After that, analyse the next node, the next node will be the no visited node with the minimum distance, in our case this node will be ‘Node D’. In this step we are going to repeat steps 2 and 3 again.

Distance table:

Important: the distance is updated only if the new distance is lower than the previous one. In this step the distance from D to C is 4 + 3 < 9, in this case the value changes to 7 and the previous node is now D.

  1. We repeat the process this time with ‘Node C’.

Distance table:

  1. We repeat the process this time with ‘Node F’.

Distance table:

  1. Finally, we analyse the last node in this case, ‘Node E’.

Distance table:

Now that we have our table with all the distances from ‘Node A’, we can find the shortest path from F. To do this, we have to find the distance from the current node F to Node A which is 10, and the path is calculated using the previous closed nodes results which are:

A -> D -> C -> F

As I said before, we can use the information in our table to find the shortest paths between A and any of the nodes in our graph. For example, between Node E and Node A the shortest path will be:

A -> D -> C -> F -> E

CODE IMPLEMENTATION

Data Structures

We are going to implement the previous algorithm using Typescript, as we have seen we need 2 main data structures to save the status:

export class Dijkstra {

    visited: Set<string>;
    dijkstraModelArray: Array<DijkstraModel>;
}

A Set, where we are going to save the visited node:

visited: Set<string>;

and an Array, where we are going to save the distances table data. In order to save this information we have created the following object:

export class DijkstraModel {

    private _currentNode: TreeNode;
    private _previousTreeNode: TreeNode | null;
    private _distant: number;
}

Algorithm

The implementation in our code is really similar to the steps I have shown you before. The only difference between our code and the steps explained is that in our code we stop as soon as we find the final node. The reason behind this decision is because we are not saving the information for future searches in order to simplify our code because the goal of this application is to show the algorithm, not the performance.

calculateShorterPath = (treeNodeArray: Array<TreeNode>) => {

        let currentNode: TreeNode | null = treeNodeArray[0];


        do {
            this.visited.add(currentNode.id);
            const distant: number = currentNode.distant;
            const currentDijkstra: DijkstraModel = new ...;
            this.dijkstraModelArray.push(currentDijkstra);
            this.iterateChild(currentDijkstra);
            currentNode = this.getNextNotVisitedNode();
        } while (!isNil(currentNode) && !currentNode.isEnd);

        if (isNil(currentNode)) return new DijkstraResModel([], []);

        const path: Array<Point> = this.createPath(currentNode);

        return new DijkstraResModel(this.dijkstraModelArray, path);
    }

We can see in our code the following steps:

  1. Save visited node
    1. Iterate child to calculate the distance
    2. Find next minimum node not visited yet
    3. Repeat until the end Node is found
    4. Create path with the previously calculated information

CONCLUSION

In conclusion, Dijkstra’s algorithm is a really good starting point because it is simple yet efficient. This algorithm could be used in a variety of different situations such as IP routing, phone network routing, geographic maps and so on…

This implementation could be improved using concurrent, we can analyse the child nodes in parallels therefore improving performance. By following the enclosed video we can see a comparison between Dijkstra, A* and the concurrent Dijkstra algorithm.

REFERENCES

Originally published on medium.com

Author's avatar
Carlos Hernandez Navarro
Programmer analyst with 3 years of work experience. For the last year, I have been designing a high performance analyst application for an aeronautical company. The main technologies used on this project are: Java Spring boot, kubernete (Openshift), Kafka, Jenkins and Oracle.
    Java
    Docker
    Scala
    AKKA HTTP
    Kafka
    AMQ STREAM
    Kubernetes
    Openshift
    Oracle
    PostgreSQL
    Cats
    Spring boot
    ElasticSearch ELK
    Jenkins
    SQL
    AWS
    TDD
    DDD
    Distributed Systems
    Microservices
    Event driven
    Functional programming

Related Issues

viebel / klipse-clj
viebel / klipse-clj
  • Open
  • 0
  • 0
  • Intermediate
  • Clojure
viebel / klipse
  • Open
  • 0
  • 0
  • Intermediate
  • Clojure
viebel / klipse
  • 1
  • 0
  • Intermediate
  • Clojure
viebel / klipse
  • Started
  • 0
  • 1
  • Intermediate
  • Clojure
  • $80
viebel / klipse
  • Open
  • 0
  • 0
  • Advanced
  • Clojure
  • $80
viebel / klipse
  • Started
  • 0
  • 2
  • Advanced
  • Clojure
  • $180
viebel / klipse
  • Started
  • 0
  • 1
  • Intermediate
  • Clojure
viebel / klipse
  • Started
  • 0
  • 3
  • Intermediate
  • Clojure
  • $80
viebel / klipse
  • 1
  • 0
  • Advanced
  • Clojure
  • $300

Get hired!

Sign up now and apply for roles at companies that interest you.

Engineers who find a new job through Functional Works average a 15% increase in salary.

Start with GithubStart with Stack OverflowStart with Email