What is Dijkstra’s Algorithm

Dijkstra’s algorithm is used to determine the shortest path or shortest distance between two nodes in a given graph, Dijkstra’s algorithm comes under the category of pathfinding algorithms and these algorithms are highly used in data transmission over the networks. If I try to make it simple, the page you are reading right now is delivered from a server which is physically located in a very long distance and when you are requesting this page the data need to go through various servers in order to reach to your machine and there may be an almost uncountable number of paths to travel,  so to determine which path that the data should travel is decided using pathfinding algorithms like Dijkstra’s algorithm.

How to Determine the Shortest Path Using Dijkstra’s Algorithm

I’ll be referring to the following weighted graph while throughout the article.  Our objective here is to find the shortest path from Node A to G

Steps of Dijkstra’s algorithm 

1. Except the Starting node for all the Other nodes set a tentative distance as infinity ( this tentative distance is something like distance from the origin (A) to a particular node, so the distance from the origin to the origin is 0 but the distance from the origin to other Nodes are not known at this point hence we put it as infinity  )

2. We will keep two sets while performing the algorithm,  first set is “Visited Nodes” and the other set is “Not Visited Nodes“

do{

3.  Loop through all the nodes and find the Node which has the lowest tentative distance ( in beginning automatically the starting point will be having the lowest tentative distance ) for that Node, consider all the not visited neighbors and then calculate the tentative distance for them. Now if the calculated values is less than the existing value for a particular neighbor node then we replace the existing value of its with the calculated value.

Ex:- we are starting from the node A right, so here is how we perform step 3 for node A

4. After step 3 the node that we considered for performing step 3 will be added to the “Visited Set” and will be removed from “Not Visited Set“

5.  if the smallest tentative distance in the nodes are infinity ( means there are no paths to the goal node ) or if the destination node has been marked as visited that means the algorithm needs to be stopped so until any of these conditions are met the algorithm continues

}while(step(5));

Now let us try to apply the algorithm to the above graph 

1. After performing step 1 and 2

except for the node A, we marked all the other node’s tentative distance as infinity, and we have two sets called Visited_Nodes = {} and Not_Visited_Nodes={A, B, C, D, E, F, G, H}

2. After doing step 3, 4

Perform step 3:  we calculate the tentative distance from node A to its neighbors which are B, C, D  and found that the calculated value is less than the values that are existing already in the nodes so we had to replace the existing values with the calculated value

Now still the goal node is not visited and the tentative distances which are available are less than the infinity so according to step 5, we are not finished.  here is the image just after doing step 5  and then back to step 3 ( just back to step 3 by selecting the lowest tentative distance (B) to start the process again )

Now since the B node is having the lowest tentative distance we perform the same steps from 3 to 5 for Node B.

At the end after some iterations  the graph looks like this at this point the goal node is in the “Visited_Nodes” and that means we are finished with looping

Here is the Java implementation of the Dijkstra’s algorithm

Below I have implemented the Dijkstra’s algorithm in java the first class is the representation of the node ( Node.java )

 

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class Node {

    public String name;
    public int tentative_distance;
    public Node Visited_from;
    public boolean is_visited = false;
    public ArrayList neighbours = new ArrayList < > ();
    public Map < string, integer = "" > distances = new HashMap < > ();

    public Node(String name, int tentative_distance) {
        this.name = name;
        this.tentative_distance = tentative_distance;
    }

    public void pushNeighbour(Node node, int distance) {
        neighbours.add(node);
        distances.put(node.name, distance);
    }

    public int calculatedTentativeDistance(Node node) {
        return distances.get(node.name) + node.tentative_distance;
    }
}

Here is how you can use this algorithm to find the shortest path for any given graph

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Demo {

    public static void main(String[] args) {

        List visited_set = new LinkedList < > ();
        List not_visited_set = new LinkedList < > ();

        Node a = new Node("A", 0);
        Node b = new Node("B", Integer.MAX_VALUE);
        Node c = new Node("C", Integer.MAX_VALUE);
        Node d = new Node("D", Integer.MAX_VALUE);
        Node e = new Node("E", Integer.MAX_VALUE);
        Node f = new Node("F", Integer.MAX_VALUE);
        Node g = new Node("G", Integer.MAX_VALUE);
        Node h = new Node("H", Integer.MAX_VALUE);

        a.pushNeighbour(b, 5);
        a.pushNeighbour(d, 6);
        a.pushNeighbour(c, 7);

        b.pushNeighbour(a, 5);
        b.pushNeighbour(c, 2);
        b.pushNeighbour(e, 10);
        b.pushNeighbour(g, 12);

        c.pushNeighbour(a, 7);
        c.pushNeighbour(b, 2);
        c.pushNeighbour(d, 2);
        c.pushNeighbour(e, 1);

        d.pushNeighbour(a, 6);
        d.pushNeighbour(c, 2);
        d.pushNeighbour(h, 4);

        e.pushNeighbour(c, 1);
        e.pushNeighbour(b, 10);
        e.pushNeighbour(f, 2);

        f.pushNeighbour(e, 2);
        f.pushNeighbour(h, 8);
        f.pushNeighbour(g, 6);

        g.pushNeighbour(b, 12);
        g.pushNeighbour(f, 6);
        g.pushNeighbour(h, 5);

        h.pushNeighbour(d, 4);
        h.pushNeighbour(f, 8);
        h.pushNeighbour(g, 5);

        not_visited_set.add(a);
        not_visited_set.add(b);
        not_visited_set.add(c);
        not_visited_set.add(d);
        not_visited_set.add(e);
        not_visited_set.add(f);
        not_visited_set.add(g);
        not_visited_set.add(h);


        while ((!visited_set.contains(g)) || (!isRemainingAllInfinity(not_visited_set))) {
            Node x = getLowestTentativeDistanceNode(not_visited_set);
            ArrayList neighbours = x.neighbours;
            for (Node neighbour: neighbours) {
                if (!neighbour.is_visited && (neighbour.calculatedTentativeDistance(x) < neighbour.tentative_distance)) {
                    neighbour.tentative_distance = neighbour.calculatedTentativeDistance(x);
                    neighbour.Visited_from = x;
                }

            }
            x.is_visited = true;
            visited_set.add(x);
            not_visited_set.remove(x);
        }

        System.out.println("Finished : " + g.tentative_distance);

        Node y = g;
        while (true) {
            System.out.print(y.name + (y.Visited_from != null ? "=>" : ""));
            y = y.Visited_from;
            if (y == null) {
                break;
            }
        }


    }

    public static boolean isRemainingAllInfinity(List not_visited) {
        for (Node a: not_visited) {
            if (a.tentative_distance < Integer.MAX_VALUE) {
                return false;
            }
        }
        return true;
    }

    public static Node getLowestTentativeDistanceNode(List not_visited_set) {
        int lowestindex = 0;
        int lowestDistance = Integer.MAX_VALUE;
        for (int x = 0; x < not_visited_set.size(); ++x) {
            if (not_visited_set.get(x).tentative_distance < lowestDistance) {
                lowestDistance = not_visited_set.get(x).tentative_distance;
                lowestindex = x;
            }
        }
        return not_visited_set.get(lowestindex);
    }



}