Ticker

20/recent/ticker-posts

Advertisement

Dijkstra's Algorithm in java

 Dijkstra's Algorithm

Dijkstra's algorithm is used to find the minimum distance between two nodes in a given graph. From a given source node the algorithm finds the shortest path to every other node of a graph. A widely used application is network routing protocols. 

How this works?



In the above graph, there are five vertices and with their edge weight from another vertex. Let us consider the source as the 0th vertex which accordingly has an edge weight of 2 to 1 and 4 to 2. But if we look at the 3rd vertex there are two possible ways from the source and the minimum one is through the 1st vertex. this algorithm chooses the shortest path to any vertex from a given source.

Algorithm:

  • Initialize an array list of type edges to hold vertex, edge, weight.
  • Initialize a distance array of size vertex and update source distance as zero and other as max.
  • Initialize a HashSet to keep track of all visited vertex.
  • Initialize a priority queue for holding the neighbouring nodes.
  • Loop until the size of HashSet is not equal to vertex and process all the neighbouring nodes.
  • Print the minimum distance array.
Creating a class graph with instance members of edge and weight and a custom comparator for comparing edge weights.


class Graph implements Comparator<Graph> {

    public int edge;
    public int distance;

    public Graph() {

    }

    public Graph(int e, int d) {
        edge = e;
        distance = d;

    }

    @Override
    public int compare(Graph o1, Graph o2) {

        if (o1.distance < o2.distance) {
            return -1;
        }
        if (o1.distance > o2.distance) {
            return 1;
        }
        return 0;

    }
}

Initializing an array list of type class Graph and multidimensional, add vertex number
array lists to the list.
Add all the elements of the graph to the list, like a list of 0th index represents the vertex 0 and add
edge and weight with help of Graph class parametrized constructor.

  public static void main(String[] args) {
        ArrayList<ArrayList<Graph>> adj = new ArrayList<ArrayList<Graph>>();
        int vertex = 5;
        for (int i = 0; i < vertex; i++) {
            ArrayList<Graph> item = new ArrayList<Graph>();
            adj.add(item);
        }
        adj.get(0).add(new Graph(12));
        adj.get(0).add(new Graph(24));
        adj.get(1).add(new Graph(31));
        adj.get(1).add(new Graph(42));
        adj.get(2).add(new Graph(33));
        Dijkstra d = new Dijkstra(vertex, adj);
        d.dijkstra(0, vertex);

    }
The below class Dijkstra initializes distance array, hash set, priority queue. process edges and prints the minimum distance.

class Dijkstra {
    public int[] dist;
    Set<Integer> set;
    PriorityQueue<Graph> pq;
    ArrayList<ArrayList<Graph>> node;

    public Dijkstra(int vertex, ArrayList<ArrayList<Graph>> node) {
        dist = new int[vertex];
        set = new HashSet<>();
        pq = new PriorityQueue<Graph>(vertex, new Graph());
        this.node = node;

    }

    void dijkstra(int src, int vertex) {

        for (int i = 0; i < vertex; i++) {
            dist[i] = Integer.MAX_VALUE;

        }
        dist[src] = 0;

        pq.add(new Graph(00));

        while (set.size() != vertex) {
            int g = pq.remove().edge;

            set.add(g);
            visitNeighbours(g);
        }
        printminDist(dist, src);

    }

    void printminDist(int[] dist, int src) {
        for (int i = 0; i < dist.length; i++) {
            System.out
                    .println("The shortest path from" + " " + src + " " + "to" + " " + i + " " + "is" + " " + dist[i]);
        }
    }

    void visitNeighbours(int u) {
        int edgeDist = -1;
        int updatedDist = -1;
        for (int i = 0; i < node.get(u).size(); i++) {
            Graph g = node.get(u).get(i);
            if (!set.contains(g.edge)) {
                edgeDist = g.distance;
                updatedDist = dist[u] + edgeDist;
                if (updatedDist < dist[g.edge]) {
                    dist[g.edge] = updatedDist;
                }

                pq.add(new Graph(g.edge, dist[g.edge]));
            }
        }
    }

}
The above program produces output like the shortest path from source to any vertex is the minimum distance to that vertex.
Ex: The shortest path from 0 to 3 is 3.

I hope you guys liked this article, here are some other articles you may like:

Post a Comment

0 Comments