Dijkstra's Algorithm

import heapq

def dijkstra(graph, start):
    """
    Dijkstra's Algorithm for Shortest Paths
    
    Args:
        graph: Dictionary {node: {neighbor: weight}}
        start: Starting node
    
    Returns:
        Dictionary {node: shortest_distance}
    """
    # Priority queue stores tuples: (distance, vertex)
    # Initialize with start node at distance 0
    pq = [(0, start)]
    
    # Dictionary to store shortest distance to each node
    # Initialize all to Infinity
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0

    while pq:
        # 1. Get the node with the smallest distance
        current_dist, current_node = heapq.heappop(pq)

        # Optimization: If we found a shorter path before, skip this stale entry
        if current_dist > distances[current_node]:
            continue

        # 2. Explore neighbors
        for neighbor, weight in graph[current_node].items():
            distance = current_dist + weight

            # 3. Relaxation: If we found a shorter path, update it
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

# Example Usage
graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'D': 3, 'E': 1},
    'C': {'B': 1, 'D': 5},
    'D': {'E': 2},
    'E': {}
}

shortest_paths = dijkstra(graph, 'A')
print(f"Shortest distances from A: {shortest_paths}")
# Output: Shortest distances from A: {'A': 0, 'B': 3, 'C': 2, 'D': 6, 'E': 4}

import java.util.*;

class Node implements Comparable<Node> {
    public String id;
    public long distance;

    public Node(String id, long distance) {
        this.id = id;
        this.distance = distance;
    }

    @Override
    public int compareTo(Node other) {
        return Long.compare(this.distance, other.distance);
    }
}

public class Dijkstra {
    public static Map<String, Long> dijkstra(Map<String, Map<String, Integer>> graph, String start) {
        // Priority queue to store nodes sorted by distance
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));

        // Map to store shortest distance to each node
        Map<String, Long> distances = new HashMap<>();
        for (String node : graph.keySet()) {
            distances.put(node, Long.MAX_VALUE);
        }
        distances.put(start, 0L);

        while (!pq.isEmpty()) {
            // 1. Get the node with the smallest distance
            Node current = pq.poll();
            String currentNode = current.id;
            long currentDist = current.distance;

            // Optimization: Skip stale entries
            if (currentDist > distances.get(currentNode)) {
                continue;
            }

            // 2. Explore neighbors
            Map<String, Integer> neighbors = graph.get(currentNode);
            if (neighbors != null) {
                for (Map.Entry<String, Integer> neighborEntry : neighbors.entrySet()) {
                    String neighbor = neighborEntry.getKey();
                    int weight = neighborEntry.getValue();
                    if (weight < 0) {
                        throw new IllegalArgumentException("Dijkstra requires non-negative weights");
                    }
                    long newDist = Math.addExact(currentDist, (long) weight);

                    // 3. Relaxation
                    if (newDist < distances.get(neighbor)) {
                        distances.put(neighbor, newDist);
                        pq.add(new Node(neighbor, newDist));
                    }
                }
            }
        }

        return distances;
    }

    public static void main(String[] args) {
        Map<String, Map<String, Integer>> graph = new HashMap<>();
        
        // Building the graph
        graph.put("A", new HashMap<>(Map.of("B", 4, "C", 2)));
        graph.put("B", new HashMap<>(Map.of("D", 3, "E", 1)));
        graph.put("C", new HashMap<>(Map.of("B", 1, "D", 5)));
        graph.put("D", new HashMap<>(Map.of("E", 2)));
        graph.put("E", new HashMap<>());

        Map<String, Long> shortestPaths = dijkstra(graph, "A");
        System.out.println("Shortest distances from A: " + shortestPaths);
        // Output: Shortest distances from A: {A=0, B=3, C=2, D=6, E=4}
    }
}