Graph — Dijkstra Shortest Path

import java.util.*;

public class Dijkstra {

    record Edge(String to, int weight) {}

    static class Graph {
        Map<String, List<Edge>> adj = new HashMap<>();

        void addEdge(String from, String to, int weight) {
            adj.computeIfAbsent(from, k -> new ArrayList<>()).add(new Edge(to, weight));
            adj.computeIfAbsent(to, k -> new ArrayList<>()).add(new Edge(from, weight));
        }

        // Dijkstra's algorithm
        Map<String, Integer> shortestPaths(String source) {
            Map<String, Integer> dist = new HashMap<>();
            PriorityQueue<Map.Entry<String, Integer>> pq =
                new PriorityQueue<>(Map.Entry.comparingByValue());

            dist.put(source, 0);
            pq.add(Map.entry(source, 0));

            while (!pq.isEmpty()) {
                var current = pq.poll();
                String node = current.getKey();
                int currentDist = current.getValue();

                if (currentDist > dist.getOrDefault(node, Integer.MAX_VALUE)) continue;

                for (Edge edge : adj.getOrDefault(node, List.of())) {
                    int newDist = currentDist + edge.weight();
                    if (newDist < dist.getOrDefault(edge.to(), Integer.MAX_VALUE)) {
                        dist.put(edge.to(), newDist);
                        pq.add(Map.entry(edge.to(), newDist));
                    }
                }
            }
            return dist;
        }

        // With path reconstruction
        record PathResult(int distance, List<String> path) {}

        PathResult shortestPath(String source, String target) {
            Map<String, Integer> dist = new HashMap<>();
            Map<String, String> prev = new HashMap<>();
            PriorityQueue<Map.Entry<String, Integer>> pq =
                new PriorityQueue<>(Map.Entry.comparingByValue());

            dist.put(source, 0);
            pq.add(Map.entry(source, 0));

            while (!pq.isEmpty()) {
                var current = pq.poll();
                String node = current.getKey();

                if (node.equals(target)) break;

                int currentDist = current.getValue();
                if (currentDist > dist.getOrDefault(node, Integer.MAX_VALUE)) continue;

                for (Edge edge : adj.getOrDefault(node, List.of())) {
                    int newDist = currentDist + edge.weight();
                    if (newDist < dist.getOrDefault(edge.to(), Integer.MAX_VALUE)) {
                        dist.put(edge.to(), newDist);
                        prev.put(edge.to(), node);
                        pq.add(Map.entry(edge.to(), newDist));
                    }
                }
            }

            // Reconstruct path
            List<String> path = new LinkedList<>();
            String current = target;
            while (current != null) {
                path.addFirst(current);
                current = prev.get(current);
            }
            return new PathResult(
                dist.getOrDefault(target, -1),
                path.getFirst().equals(source) ? path : List.of()
            );
        }
    }

    public static void main(String[] args) {
        Graph g = new Graph();
        g.addEdge("A", "B", 4);
        g.addEdge("A", "C", 2);
        g.addEdge("B", "D", 3);
        g.addEdge("C", "B", 1);
        g.addEdge("C", "D", 5);
        g.addEdge("D", "E", 1);

        var distances = g.shortestPaths("A");
        distances.forEach((node, dist) ->
            System.out.printf("A → %s: %d%n", node, dist));

        var result = g.shortestPath("A", "E");
        System.out.printf("\nA → E: distance=%d, path=%s%n",
            result.distance(), result.path());
    }
}