NUHMAN.com

Dijkstra’s Algorithm in Java

Dijkstra’s algorithm is one of the most popular solutions for finding the shortest path from a source node to all other nodes in a weighted graph. It’s particularly effective when dealing with non-negative edge weights.

🚦 How It Works

1. Initialize Distances: Distance to source = 0, others = ∞
2. Use a Priority Queue (Min-Heap): Always pick the vertex with the smallest known distance.
3. Relaxation: For each neighbor, check if the new path is shorter. If yes, update the distance.
4. Repeat until all nodes are visited.

🛠️ Java Implementation

Edge Class

java

class Edge {
    int target;
    int weight;

    public Edge(int target, int weight) {
        this.target = target;
        this.weight = weight;
    }
}

Node Class (for Priority Queue)

java

class Node {
    int vertex;
    int distance;

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

Graph Class

java

import java.util.*;

class Graph {
    private Map<Integer, List<Edge>> adjList;

    public Graph() {
        this.adjList = new HashMap<>();
    }

    public void addEdge(int source, int target, int weight) {
        adjList.putIfAbsent(source, new ArrayList<>());
        adjList.putIfAbsent(target, new ArrayList<>());
        adjList.get(source).add(new Edge(target, weight));
        adjList.get(target).add(new Edge(source, weight)); // Undirected graph
    }

    public Map<Integer, Integer> dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.distance));
        Map<Integer, Integer> distances = new HashMap<>();
        Set<Integer> visited = new HashSet<>();

        for (int vertex : adjList.keySet()) {
            distances.put(vertex, Integer.MAX_VALUE);
        }
        distances.put(start, 0);
        pq.offer(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            int currentVertex = currentNode.vertex;

            if (!visited.add(currentVertex)) continue;

            for (Edge edge : adjList.get(currentVertex)) {
                if (!visited.contains(edge.target)) {
                    int newDist = distances.get(currentVertex) + edge.weight;

                    if (newDist < distances.get(edge.target)) {
                        distances.put(edge.target, newDist);
                        pq.offer(new Node(edge.target, newDist));
                    }
                }
            }
        }

        return distances;
    }
}

🧪 Example Usage

java

public class DijkstraExample {
    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addEdge(0, 1, 4);
        graph.addEdge(0, 2, 1);
        graph.addEdge(2, 1, 2);
        graph.addEdge(1, 3, 1);
        graph.addEdge(2, 3, 5);
        graph.addEdge(3, 4, 3);

        Map<Integer, Integer> distances = graph.dijkstra(0);

        for (Map.Entry<Integer, Integer> entry : distances.entrySet()) {
            System.out.println("Distance from 0 to " + entry.getKey() + " is " + entry.getValue());
        }
    }
}

🖨️ Sample Output

vbnet

Distance from 0 to 0 is 0  
Distance from 0 to 1 is 3  
Distance from 0 to 2 is 1  
Distance from 0 to 3 is 4  
Distance from 0 to 4 is 7

📌 Key Points

• Time Complexity: O((V + E) log V)
• Space Complexity: O(V)
• Uses a priority queue for optimal efficiency
• Great for non-negative weighted graphs