Implementing Dijkstra's Algorithm

Introduction

In this lab, we're going to implement Dijkstra's Algorithm in Java. Dijkstra's Algorithm is a popular algorithm used to solve the shortest-path problem for a weighted graph.

Create a Graph Class

In this step, we'll create a class called Graph that will represent our weighted graph. We'll create a 2-D adjacency matrix in this class to represent the edges of the graph.

class Graph
{
    int[][] adjMatrix; // adjacency matrix to represent the edges
    int numOfvertices;

    Graph(int[][] mat, int v)
    {
        this.adjMatrix = mat;
        this.numOfvertices = v;
    }

    void addEdge(int src, int dest, int edgeWeight)
    {
        adjMatrix[src][dest] = edgeWeight;
        adjMatrix[dest][src] = edgeWeight;
    }
}

Implement Dijkstra's Algorithm

In this step, we'll implement Dijkstra's algorithm in Java. Let's create a helper method called getClosestVertex to find the closest unvisited node. We'll also implement the main algorithm in a dijkstrasShortestPath method. This method will take a Graph and a source vertex as parameters and return the shortest-distance array.

public static int getClosestVertex(int[] distance, boolean[] visited) {
    int min = Integer.MAX_VALUE;
    int minIdx = -1;
    for(int i=0; i<distance.length; i++) {
        if(distance[i] < min)
            if(visited[i] == false) {
                min = distance[i];
                minIdx = i;
            }
    }
    return minIdx;
}

public static int[] dijkstrasShortestPath(Graph g, int src) {
    // final shortest distance array
    int[] distance = new int[g.numOfvertices];
    // array to tell whether shortest distance of vertex has been found
    boolean[] visited = new boolean[g.numOfvertices];

    // initializing the arrays
    for(int i=0; i<g.numOfvertices; i++) {
        distance[i] = Integer.MAX_VALUE; // initial distance is infinite
        visited[i] = false; // shortest distance for any node has not been found yet
    }
    distance[src] = 0;

    for(int i=0; i<g.numOfvertices; i++) {
        int closestVertex = getClosestVertex(distance, visited); // get the closest node
        if(closestVertex == Integer.MAX_VALUE) // if closest node is infinite distance away, it means that no other node can be reached. So return
            return distance;

        visited[closestVertex] = true;
        for(int j=0; j<g.numOfvertices; j++) {
            if(visited[j] == false) // shortest distance of the node j should not have been finalized
            {
                if(g.adjMatrix[closestVertex][j] != 0) {
                    int d = distance[closestVertex] + g.adjMatrix[closestVertex][j];
                    if(d < distance[j]) // distance via closestVertex is less than the initial distance
                        distance[j] = d;
                }
            }
        }
    }
    return distance;
}

Test Our Implementation

In this step, we'll test our implementation by creating a main method that will add edges to our graph and call our dijkstrasShortestPath method to find the shortest distance from a source vertex to all other vertices of a weighted graph.

public static void main(String[] args) {
    int numOfVertices = 6;
    int[][] adjMat = new int[6][6];
    Graph graph = new Graph(adjMat, numOfVertices);

    // add edges to the graph
    graph.addEdge(0, 4, 21);
    graph.addEdge(0, 3, 18);
    graph.addEdge(2, 1, 7);
    graph.addEdge(1, 4, 6);
    graph.addEdge(4, 5, 10);
    graph.addEdge(4, 3, 11);
    graph.addEdge(5, 3, 7);

    // call Dijkstra's algorithm to find shortest distance
    int[] dist = dijkstrasShortestPath(graph, 0);
    System.out.print(Arrays.toString(dist));
}

Compile and run the above code to get the shortest-distance array [0, 27, 34, 18, 21, 25].

Summary

Congratulations! You have completed the Implementing Dijkstra's Algorithm lab. You can practice more labs in LabEx to improve your skills.