This Java program demonstrates the implementation of Dijkstra’s algorithm to find the shortest paths from a single source vertex to all other vertices in a graph with non-negative weights. The algorithm uses a priority queue to continually select the vertex with the shortest known distance from the source.

Java Code

import java.util.*;

class Graph {
    private int V; // Number of vertices
    private List<List<Node>> adjList;

    public Graph(int V) {
        this.V = V;
        adjList = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int src, int dest, int weight) {
        adjList.get(src).add(new Node(dest, weight));
    }

    public void dijkstra(int src) {
        PriorityQueue<Node> pq = new PriorityQueue<>(V, new Node());
        int[] dist = new int[V];

        Arrays.fill(dist, Integer.MAX_VALUE);
        pq.add(new Node(src, 0));
        dist[src] = 0;

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int u = node.vertex;

            for (Node adjacent : adjList.get(u)) {
                int v = adjacent.vertex;
                int weight = adjacent.weight;
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.add(new Node(v, dist[v]));
                }
            }
        }

        printSolution(dist, src);
    }

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

    class Node implements Comparator<Node> {
        public int vertex, weight;

        public Node() {
        }

        public Node(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }

        @Override
        public int compare(Node node1, Node node2) {
            if (node1.weight > node2.weight)
                return 1;
            if (node1.weight < node2.weight)
                return -1;
            return 0;
        }
    }
}

public class DijkstrasAlgorithm {
    public static void main(String[] args) {
        int V = 5;
        Graph g = new Graph(V);
        g.addEdge(0, 1, 9);
        g.addEdge(0, 2, 6);
        g.addEdge(0, 3, 5);
        g.addEdge(0, 4, 3);
        g.addEdge(2, 1, 2);
        g.addEdge(2, 3, 4);

        g.dijkstra(0);
    }
}

Explanation of the Code

The program defines a Graph class which includes:

• Graph Structure: Represents the graph using an adjacency list where each node is represented as a pair (vertex, weight).
• addEdge: Method to add an edge between two vertices with a given weight.
• dijkstra: Implements Dijkstra’s algorithm using a priority queue. It keeps track of the minimum distance from the source to each vertex and updates distances based on the currently processed vertex’s adjacent nodes.
• Node Class: Used for the priority queue to store the vertex and its current shortest distance. It includes a comparator to order nodes by their weights.
• printSolution: Outputs the shortest distance from the source to each vertex.

This setup ensures that the shortest path distances are efficiently computed and easy to retrieve, making Dijkstra’s algorithm a powerful tool for graph analysis in many applications such as network routing protocols.