Dijkstra’s Algorithm implementation in java

     Dijkstra is an algorithm in data structures. It finds the shortest path from the source node to other nodes in a graph. One condition is it should have non- negative weight.

Here, it comes the implementation in java.

Program implementation:

              This program starts from including the built-in package java.util.*.

• A class is created with Node implementation. It includes two variables g_vertex,g_weight.
• The constructor initialises the variable.
• ‘compareTo()’ -it compares the two integer variable and returns the value.
• ‘dijkstra()’ – This function has following activities.
• First, graph length is identified.
• ‘dist’ -  it is a array with finds the distance.
• ‘n_visited’ – it sets whether the node is visited or not.
• A priority queue is created.
• An array is filled with distance.
• The shortest path is found out and added to priority queue.
• The distance and vertex is displayed.
• ‘main()’ – it creates the graph input and calls the dijkstra() function.

Program:

import java.util.*;

class DijkstraEg {

    static class Node implements Comparable<Node> {

        int g_vertex, g_weight;

        Node(int g_vertex, int g_weight) {

            this.g_vertex = g_vertex;

            this.g_weight = g_weight;

        }

        public int compareTo(Node other) {

            return Integer.compare(this.g_weight, other.g_weight);

        }

    }

    public static void dijkstra(int[][] graph, int src1) {

        int V = graph.length;

        int[] dist = new int[V];

        boolean[] n_visited = new boolean[V];

        PriorityQueue<Node> pq1 = new PriorityQueue<>();

        Arrays.fill(dist, Integer.MAX_VALUE);

        dist[src1] = 0;

        pq1.add(new Node(src1, 0));

        while (!pq1.isEmpty()) {

            Node current = pq1.poll();

            int u = current.g_vertex;

            if (n_visited[u]) continue;

            n_visited[u] = true;

            for (int v = 0; v < V; v++) {

                if (graph[u][v] != 0 && !n_visited[v] && dist[u] + graph[u][v] < dist[v]) {

                    dist[v] = dist[u] + graph[u][v];

                    pq1.add(new Node(v, dist[v]));

                }

            }

        }

        System.out.println("Vertex \t Distance from Source");

        for (int i = 0; i < V; i++) {

            System.out.println(i + " \t " + dist[i]);

        }

    }

    public static void main(String[] args) {

        int[][] graph = {

            {0, 05, 10, 0, 15},

            {05, 0, 14, 16, 0},

            {2, 6, 0, 12, 0},

            {07, 16, 11, 0, 18},

            {0, 8, 10, 14, 17}

        };

        dijkstra(graph, 0);

    }

}

Output:

C:\raji\blog>javac DijkstraEg.java

C:\raji\blog>java DijkstraEg

Vertex   Distance from Source

0        0

1        5

2        10

3        21

4        15

Thus, the java implementation of Dijkstra’s algorithm is done. Hope, this code is useful to you. Happy coding!!!!