How To Implement Dijkstra’s Algorithm In Java

This Tutorial Explains how to Implement the Dijkstra’s algorithm in Java to find the Shortest Routes in a Graph or a Tree with the help of Examples:

In our earlier tutorial on Graphs in Java, we saw that graphs are used to find the shortest path between the nodes apart from other applications.

To find the shortest path between two nodes of a graph, we mostly employ an algorithm known as “Dijkstra’s Algorithm”. This algorithm remains the widely used algorithm to find the shortest routes in a graph or a tree.

=> Check ALL Java Tutorials Here

Dijkstra’s Algorithm In Java

Given a weighted graph and a starting (source) vertex in the graph, Dijkstra’s algorithm is used to find the shortest distance from the source node to all the other nodes in the graph.

As a result of the running Dijkstra’s algorithm on a graph, we obtain the shortest path tree (SPT) with the source vertex as root.

In Dijkstra’s algorithm, we maintain two sets or lists. One contains the vertices that are a part of the shortest-path tree (SPT) and the other contains vertices that are being evaluated to be included in SPT. Hence for every iteration, we find a vertex from the second list that has the shortest path.

The pseudocode for the Dijkstra’s shortest path algorithm is given below.

Pseudocode

Given below is the pseudocode for this algorithm.

procedure dijkstra(G, S)
     G-> graph; S->starting vertex
begin
    for each vertex V in G			//initialization; initial path set to infinite
        path[V] <- infinite
        previous[V] <- NULL
        If V != S, add V to Priority Queue PQueue
    path [S] <- 0
	
    while PQueue IS NOT EMPTY
        U <- Extract MIN from PQueue
        for each unvisited adjacent_node  V of U
            tempDistance <- path [U] + edge_weight(U, V)
            if tempDistance < path [V]
                path [V] <- tempDistance
                previous[V] <- U
    return path[], previous[]
end

Let’s now take a sample graph and illustrate the Dijkstra’s shortest path algorithm.

Initially, the SPT (Shortest Path Tree) set is set to infinity.

Let’s start with vertex 0. So to begin with we put the vertex 0 in sptSet.

sptSet = {0, INF, INF, INF, INF, INF}.

Next with vertex 0 in sptSet, we will explore its neighbors. Vertices 1 and 2 are two adjacent nodes of 0 with distance 2 and 1 respectively.

In the above figure, we have also updated each adjacent vertex (1 and 2) with their respective distance from source vertex 0. Now we see that vertex 2 has a minimum distance. So next we add vertex 2 to the sptSet. Also, we explore the neighbors of vertex 2.

Now we look for the vertex with minimum distance and those that are not there in spt. We pick vertex 1 with distance 2.

As we see in the above figure, out of all the adjacent nodes of 2, 0, and 1 are already in sptSet so we ignore them. Out of the adjacent nodes 5 and 3, 5 have the least cost. So we add it to the sptSet and explore its adjacent nodes.

In the above figure, we see that except for nodes 3 and 4, all the other nodes are in sptSet. Out of 3 and 4, node 3 has the least cost. So we put it in sptSet.

As shown above, now we have only one vertex left i.e. 4 and its distance from the root node is 16. Finally, we put it in sptSet to get the final sptSet = {0, 2, 1, 5, 3, 4} that gives us the distance of each vertex from the source node 0.

Implementation Of Dijkstra’s Algorithm In Java

Implementation of Dijkstra’s shortest path algorithm in Java can be achieved using two ways. We can either use priority queues and adjacency list or we can use adjacency matrix and arrays.

In this section, we will see both the implementations.

Using A Priority Queue

In this implementation, we use the priority queue to store the vertices with the shortest distance. The graph is defined using the adjacency list. A sample program is shown below.

import java.util.*; 
class Graph_pq { 
    int dist[]; 
    Set<Integer> visited; 
    PriorityQueue<Node> pqueue; 
    int V; // Number of vertices 
    List<List<Node> > adj_list; 
    //class constructor
    public Graph_pq(int V) { 
        this.V = V; 
        dist = new int[V]; 
        visited = new HashSet<Integer>(); 
        pqueue = new PriorityQueue<Node>(V, new Node()); 
    } 
  
    // Dijkstra's Algorithm implementation 
    public void algo_dijkstra(List<List<Node> > adj_list, int src_vertex) 
    { 
        this.adj_list = adj_list; 
  
        for (int i = 0; i < V; i++) 
            dist[i] = Integer.MAX_VALUE; 
  
        // first add source vertex to PriorityQueue 
        pqueue.add(new Node(src_vertex, 0)); 
  
        // Distance to the source from itself is 0 
        dist[src_vertex] = 0; 
        while (visited.size() != V) { 

   // u is removed from PriorityQueue and has min distance  
            int u = pqueue.remove().node; 
  
            // add node to finalized list (visited)
            visited.add(u); 
            graph_adjacentNodes(u); 
        } 
    } 
  // this methods processes all neighbours of the just visited node 
    private void graph_adjacentNodes(int u)   { 
        int edgeDistance = -1; 
        int newDistance = -1; 
  
        // process all neighbouring nodes of u 
        for (int i = 0; i < adj_list.get(u).size(); i++) { 
            Node v = adj_list.get(u).get(i); 
  
            //  proceed only if current node is not in 'visited'
            if (!visited.contains(v.node)) { 
                edgeDistance = v.cost; 
                newDistance = dist[u] + edgeDistance; 
  
                // compare distances 
                if (newDistance < dist[v.node]) 
                    dist[v.node] = newDistance; 
  
                // Add the current vertex to the PriorityQueue 
                pqueue.add(new Node(v.node, dist[v.node])); 
            } 
        } 
    } 
}
class Main{
    public static void main(String arg[])   { 
        int V = 6; 
        int source = 0; 
        // adjacency list representation of graph
        List<List<Node> > adj_list = new ArrayList<List<Node> >(); 
        // Initialize adjacency list for every node in the graph 
        for (int i = 0; i < V; i++) { 
            List<Node> item = new ArrayList<Node>(); 
            adj_list.add(item); 
        } 

  
        // Input graph edges 
        adj_list.get(0).add(new Node(1, 5)); 
        adj_list.get(0).add(new Node(2, 3)); 
        adj_list.get(0).add(new Node(3, 2)); 
        adj_list.get(0).add(new Node(4, 3));
        adj_list.get(0).add(new Node(5, 3));
        adj_list.get(2).add(new Node(1, 2)); 
        adj_list.get(2).add(new Node(3, 3)); 
        // call Dijkstra's algo method  
        Graph_pq dpq = new Graph_pq(V); 
        dpq.algo_dijkstra(adj_list, source); 
  
        // Print the shortest path from source node to all the nodes 
        System.out.println("The shorted path from source node to other nodes:"); 
        System.out.println("Source\t\t" + "Node#\t\t" + "Distance");
        for (int i = 0; i < dpq.dist.length; i++) 
            System.out.println(source + " \t\t " + i + " \t\t "  + dpq.dist[i]); 
    } 
} 
  
// Node class  
class Node implements Comparator<Node> { 
    public int node; 
    public int cost; 
    public Node() { } //empty constructor 
  
    public Node(int node, int cost) { 
        this.node = node; 
        this.cost = cost; 
    } 
    @Override
    public int compare(Node node1, Node node2) 
    { 
        if (node1.cost < node2.cost) 
            return -1; 
        if (node1.cost > node2.cost) 
            return 1; 
        return 0; 
    } 
}

Output:

Using Adjacency Matrix

In this approach, we use the adjacency matrix to represent the graph. For spt set we use arrays.

The following program shows this implementation.

import java.util.*; 
import java.lang.*; 
import java.io.*; 
  
class Graph_Shortest_Path { 
    
    static final int num_Vertices = 6;  //max number of vertices in graph
    // find a vertex with minimum distance
    int minDistance(int path_array[], Boolean sptSet[])   { 
        // Initialize min value 
        int min = Integer.MAX_VALUE, min_index = -1; 
        for (int v = 0; v < num_Vertices; v++) 
            if (sptSet[v] == false && path_array[v] <= min) { 
                min = path_array[v]; 
                min_index = v; 
            } 
  
        return min_index; 
    } 
  
    // print the array of distances (path_array)
    void printMinpath(int path_array[])   { 
        System.out.println("Vertex# \t Minimum Distance from Source"); 
        for (int i = 0; i < num_Vertices; i++) 
            System.out.println(i + " \t\t\t " + path_array[i]); 
    }
   
// Implementation of Dijkstra's algorithm for graph (adjacency matrix) 
    void algo_dijkstra(int graph[][], int src_node)  { 
        int path_array[] = new int[num_Vertices]; // The output array. dist[i] will hold 
        // the shortest distance from src to i 
  
        // spt (shortest path set) contains vertices that have shortest path 
        Boolean sptSet[] = new Boolean[num_Vertices]; 
  
        // Initially all the distances are INFINITE and stpSet[] is set to false 
        for (int i = 0; i < num_Vertices; i++) { 
            path_array[i] = Integer.MAX_VALUE; 
            sptSet[i] = false; 
        } 
  
        // Path between vertex and itself is always 0 
        path_array[src_node] = 0; 
   // now find shortest path for all vertices  
        for (int count = 0; count < num_Vertices - 1; count++) { 
            // call minDistance method to find the vertex with min distance
            int u = minDistance(path_array, sptSet); 
              // the current vertex u is processed
            sptSet[u] = true; 
              // process adjacent nodes of the current vertex
            for (int v = 0; v < num_Vertices; v++) 
  
                // if vertex v not in sptset then update it  
                if (!sptSet[v] && graph[u][v] != 0 && path_array[u] != 
                            Integer.MAX_VALUE && path_array[u] 
                            + graph[u][v] < path_array[v]) 
                            path_array[v] = path_array[u] + graph[u][v]; 
        } 
  
        // print the path array 
        printMinpath(path_array); 
    } 
}
class Main{
    public static void main(String[] args) 
    { 
        //example graph is given below
        int graph[][] = new int[][] { { 0, 2, 1, 0, 0, 0}, 
                                      { 2, 0, 7, 0, 8, 4}, 
                                      { 1, 7, 0, 7, 0, 3}, 
                                      { 0, 0, 7, 0, 8, 4}, 
                                      { 0, 8, 0, 8, 0, 5}, 
                                      { 0, 4, 3, 4, 5, 0} }; 
        Graph_Shortest_Path g = new Graph_Shortest_Path(); 
        g.algo_dijkstra(graph, 0); 
    } 
}

Output:

Frequently Asked Questions

Q #1) Does Dijkstra work for undirected graphs?

Answer: If the graph is directed or undirected does not matter in the case of Dijkstra’s algorithm. This algorithm is concerned only about the vertices in the graph and the weights.

Q #2) What is the time complexity of Dijkstra’s algorithm?

Answer: Time Complexity of Dijkstra’s Algorithm is O (V 2). When implemented with the min-priority queue, the time complexity of this algorithm comes down to O (V + E l o g V).

Q #3) Is Dijkstra a greedy algorithm?

Answer: Yes, Dijkstra is a greedy algorithm. Similar to Prim’s algorithm of finding the minimum spanning tree (MST) these algorithms also start from a root vertex and always chooses the most optimal vertex with the minimum path.

Q #4) Is Dijkstra DFS or BFS?

Answer: It is neither. But as Dijkstra’s algorithm uses a priority queue for its implementation, it can be viewed as close to BFS.

Q #5) Where is the Dijkstra algorithm used?

Answer: It is used mostly in routing protocols as it helps to find the shortest path from one node to another node.

Conclusion

In this tutorial, we have discussed the Dijkstra’s algorithm. We use this algorithm to find the shortest path from the root node to the other nodes in the graph or a tree.

We usually implement Dijkstra’s algorithm using a Priority queue as we have to find the minimum path. We can also implement this algorithm using the adjacency matrix. We have discussed both these approaches in this tutorial.

We hope you will find this tutorial helpful.

=> Visit Here To See The Java Training Series For All