1. Introduction

Dijkstra’s Algorithm is a classic graph algorithm that is used to find the shortest path from a starting node to all other nodes in a weighted graph. The algorithm works on both directed and undirected graphs. However, it does not account for negative weights. In this blog post, we’ll delve into its implementation in Java.

2. Program Steps

1. Represent the graph using an adjacency matrix.

2. Initialize a distance array with Integer.MAX_VALUE (considered as infinity) for all nodes except the starting node which will have a distance of 0.

3. Use a boolean array sptSet (shortest path tree set) to keep track of vertices for which the shortest distance is finalized.

4. For each vertex not yet included in sptSet, choose a vertex with the minimum distance value.

5. Update the distance value of the adjacent vertices of the chosen vertex.

6. Repeat the process for all the vertices.

3. Code Program

class DijkstraAlgorithm {
    private static final int V = 5;  // Number of vertices in the graph

    // Utility function to find the vertex with minimum distance
    private int minDistance(int[] dist, boolean[] sptSet) {
        int min = Integer.MAX_VALUE, minIndex = -1;

        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && dist[v] <= min) {
                min = dist[v];
                minIndex = v;
            }
        }
        return minIndex;
    }

    public void dijkstra(int[][] graph, int src) {
        int[] dist = new int[V];  // Output array. dist[i] holds shortest distance from src to i
        boolean[] sptSet = new boolean[V];

        for (int i = 0; i < V; i++) {
            dist[i] = Integer.MAX_VALUE;
            sptSet[i] = false;
        }

        dist[src] = 0;

        for (int count = 0; count < V - 1; count++) {
            int u = minDistance(dist, sptSet);
            sptSet[u] = true;

            for (int v = 0; v < V; v++) {
                if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }

        printSolution(dist);
    }

    private void printSolution(int[] dist) {
        System.out.println("Vertex \t\t Distance from Source");
        for (int i = 0; i < V; i++) {
            System.out.println(i + " \t\t " + dist[i]);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        int[][] graph = new int[][]{
            {0, 4, 0, 0, 0},
            {4, 0, 8, 0, 0},
            {0, 8, 0, 7, 0},
            {0, 0, 7, 0, 9},
            {0, 0, 0, 9, 0}
        };

        DijkstraAlgorithm dijkstra = new DijkstraAlgorithm();
        dijkstra.dijkstra(graph, 0);
    }
}

Output:

Vertex 		 Distance from Source
0 		 0
1 		 4
2 		 12
3 		 19
4 		 28

4. Step By Step Explanation

1. The given graph is represented using an adjacency matrix. A value of 0 indicates no direct edge between the vertices.

2. The minDistance method finds the vertex with the minimum distance from the source, among the set of vertices not yet included in the shortest path tree.

3. The dijkstra method calculates the shortest path from a source vertex to every other vertex. It iteratively finalizes the shortest distance for every vertex.

4. During each iteration, it picks a vertex which is not in the sptSet and has a minimum distance from the source.

5. For every adjacent vertex v, if the sum of the current distance value of u and the weight of edge u-v, is less than the distance value of v, then update the distance value of v.

6. The printSolution method outputs the shortest distance of each vertex from the source vertex.

7. The Main class creates a sample graph and initiates the Dijkstra's algorithm on it. The output represents the shortest path from vertex 0 to every other vertex in the graph.