Dijkstra Algorithm Implementation in Java

In my last article on a custom implementation of Graph data structure, we discussed the adjacency list representation of Graph and performed multiple operations such as insertion, search and BFS traversal. In this article, we will discuss another representation of Graph, i.e. Adjacency Matrix and use this representation to find the shortest path in a weighted graph using Dijkstra's algorithm.

What is Dijkstra Algorithm

Dijkstra algorithm is a generalization of BFS algorithm to find the shortest paths between nodes in a graph. For a given graph G = (V, E) and a distinguished vertex s, then we can find the shortest path from s to every other vertex in G with the help of Dijkstra algorithm.

This algorithm uses the greedy method as it always picks the next closest vertex to the source.

Dijkstra Algorithm Details

• Any vertex can be selected as a source vertex and distance between a source vertex to itself is zero.
• Initially, we assume all the other vertex are at a distance of infinity.
• Next, we find the direct neighbouring vertex of the source vertex which is at a minimum distance. Let us assume, a vertex has 2 different neighbouring vertexes A and B at a distance of 2 and 4 then the minimum distance vertex is A in this case.
• We mark this vertex as a visited vertex and calculate the distance of each direct neighbouring vertex.
• If the sum of the distance of minimum vertex (d[u]) and cost of edge to neighbouring vertex(c[u, v]) is less then the distance of v(d[v]), then we update the distance of neighbouring vertex as the sum of the distance of minimum vertex (d[u]) and cost of edge to neighbouring vertex(c[u, v]).

  if(d[u] + c[u, v] < d[v]) -> d[v] = d[u] + c[u, v]
  

  This algorithm always selects the shortest path and updates another vertex if above condition matches.
• We repeat this process until we visit all the vertex of a given graph.

We will apply Dijkstra algorithm on below graph.

Lett us apply this algorithm.

Let us assume the source vertex is 0 and the distance of all other vertex is infinity.

Now, let us calculate the distance of each neighbouring vertex from the source vertex 0 and apply the above formula and if the condition matches we will update the weight of the neighbouring vertex.

Now, the min distance is at vertex 1 and hence let us update all it's neighbouring vertex if d[u] + c[u, v] < d[v]. The weight of vertex 2 is updated now as the distance of source vertex(4) + cost of source vertex to neighbour vertex(2) is less then tthe distance of neighbour vertex 2 which is 8.

Distance of other vertex is also updated as all other neighbour vertices are at infinity.

At last, our final graph should look like this after applying Dijkstra algorithm.

Matrix Representation of Graph for Dijkstra Algorithm

Now, to start with our Java implementation for Dijkstra algorithm we will first represent our above graph in a matrix form.

If we represent the vertex as A, B, C , D and E for the vertex 0, 1, 2, 3, and 4 then below matrix represent our above graph.

Each row represents a vertex of the Graph and the number of vertices is the length of the matrix. Now a combination of row and column defines an edge between vertices.

Now, let us start our Java implementation. We have 2 arrays of size equal to the no of vertex of the graph - one is to store the visited vertex and another one to store the distance from the source vertex to other vertices.

package com.devglan.graph;

public class Dijkstra {

    public static void dijkstra(int[][] graph, int sourceVertex){
        int vertexCount = graph.length;
        boolean[] visitedVertex = new boolean[vertexCount];
        int[] distance = new int[vertexCount];
        for (int i = 0; i < vertexCount; i++){
            visitedVertex[i] = false;
            distance[i] = Integer.MAX_VALUE;
        }
        distance[sourceVertex] = 0; // distance of source vertex to itself is zero
        for (int i = 0; i < vertexCount; i++){
            //find the neighbouring unvisited vertex having  minimum distance from source vertex
            //for the first time u will be the source vertex and the distance array will be updated with the neighbouring vertex distance of source vertex
            int u = findMinDistance(distance, visitedVertex);
            //u is the row and v is the column
            visitedVertex[u] = true;
            //now update all the neighbour vertex distances
            for (int v =0 ; v < vertexCount; v++){
            //graph[u][v] != 0 -> there should be a direct edge
                if(!visitedVertex[v] && graph[u][v] != 0 && (distance[u] + graph[u][v] < distance[v])){
                    distance[v] = distance[u] + graph[u][v];
                }
            }
        }
        for (int i = 0; i < distance.length; i++){
            System.out.println(String.format("Distance from source vertex %s to vertex %s is %s", sourceVertex, i, distance[i]));
        }

    }

    private static int findMinDistance(int[] distance, boolean[] visitedVertex) {
        int minDistance = Integer.MAX_VALUE;
        int minDistanceVertex = -1;
        for (int i =0; i < distance.length; i++){
            //the vertex should not be visited and the distance should be the minimum.
            //this is similar to finding the min element of an array
            if(!visitedVertex[i] && distance[i] < minDistance){
                minDistance = distance[i];
                minDistanceVertex = i;
            }
        }
        return minDistanceVertex;
    }

    public static void main(String[] args) {
        int graph[][] = new int[][] { { 0, 4, 8, 0, 0 },
                { 4, 0, 2, 5, 0 },
                { 8, 2, 0, 5, 9},
                { 0, 5, 5, 0, 4 },
                { 0, 0, 9, 4, 0 } };
        Dijkstra t = new Dijkstra();
        t.dijkstra(graph, 0);
    }
}

First, we mark all the vertices as visited to false and the distance to be infinity.

As discussed above, the distance between source vertex to itself is zero and hence the distance array is updated to 0 for the source vertex.

Next, find a neighbouring unvisited vertex having a minimum distance from source vertex. For the very first iteration to find a minimum distance, this will be the source vertex itself and hence the distance array will be updated with the cost of the edge of the neighboring vertex from the source vertex as the all the distances are assumed to be infinity during first iteration and hence it satisfies the condition (d[u] + c[u, v] < d[v]).

To update the distance of neighboring vertex, traverse all the neighbors of this vertex. In the matrix representation, the neighbors of the min vertex are present in the same row. Hence, iterate each element of the row(meaning column-wise for this row) and update the distance array.

From the second iteration to find the minimum distance, the source vertex is already visited and hence the min distant vertex is calculated from the neighbor vertices of the source vertex.

Once the min distant vertex is calculated again, all the distance of the neighboring vertices from this min distant vertex is calculated and their weight is updated if required based on the above formula

graph[u][v] != 0 condition is required to check if there exists a direct edge from vertex u to vertex v.

Disadvantages of Dijkstra Algorithm

• It is a greedy search algorithm thereby wasting time and memory.
• It cannot handle negative edges.

We use Bellman-Ford algorithm to find the shortest paths between nodes that can handle negative edges too. It uses the same concept as that of Dijkstra algorithm but requires more running time than Dijkstra's algorithm.

Conclusion

In this article, we discussed about how we can implement Dijkstra algorithm in Java to find the shortest paths between nodes in a graph.