Dijkstra's algorithm- Java

Dijkstra's algorithm is a shortest-path algorithm that finds the shortest path from a source vertex to all other vertices in a weighted graph. Here is a basic implementation of Dijkstra's algorithm in Java:

import java.util.*;

class Dijkstra {
    static final int V = 9;

    int minDistance(int dist[], Boolean sptSet[]) {
        int min = Integer.MAX_VALUE, min_index = -1;

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

        return min_index;
    }

    void dijkstra(int graph[][], int src) {
        int dist[] = new int[V];
        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];
        }

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

    public static void main(String[] args) {
        int graph[][] = new int[][] { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
                                      { 4, 0, 8, 0, 0, 0, 0, 11, 0 },
                                      { 0, 8, 0, 7, 0, 4, 0, 0, 2 },
                                      { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
                                      { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
                                      { 0, 0, 4, 14, 10, 0, 2, 0, 0 },
                                      { 0, 0, 0, 0, 0, 2, 0, 1, 6 },
                                      { 8, 11, 0, 0, 0, 0, 1, 0, 7 },
                                      { 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
        Dijkstra t = new Dijkstra();
        t.dijkstra(graph, 0);
    }
}

The above implementation of Dijkstra's algorithm in Java uses an array dist[] to store the distances from the source vertex to all other vertices, and an array sptSet[] to keep track of vertices included in the shortest path tree. The method minDistance() returns the vertex with the minimum distance value that is not yet included in the shortest path tree. The main method dijkstra implements the algorithm:

1. Initialize all distances as infinite and the source vertex distance as 0.

2. While there are vertices not yet included in the shortest path tree, select the vertex with the minimum distance that is not yet included and mark it as included.

3. For all vertices connected to the selected vertex, if their current distance is greater than the sum of the selected vertex's distance and the weight of the edge connecting them, update their distance.

4. Repeat steps 2 and 3 until all vertices are included in the shortest path tree.

Time complexity: O(V^2), where V is the number of vertices in the graph. This is because the algorithm repeatedly selects the minimum distance vertex, which takes O(V) time, and updates the distances of all its neighbors, which takes O(V) time as well. Space complexity: O(V), as we need to store the distances of all vertices and the information of whether a vertex is included in the shortest path tree or not.

Here's an example of the output of the code:
Enter the number of vertices: 5
Enter the adjacency matrix:
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
Enter the source vertex: 0
Vertex   Distance from Source
0               0
1               4
2               12
3               19
4               21

In this example, the input is a graph with 5 vertices and the adjacency matrix representing the graph. The source vertex is 0. The output shows the minimum distance from the source vertex to each vertex in the graph.