ShortestPathSolver.java

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class ShortestPathSolver {

    static class Edge {
        int to;
        int weight;

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

    static class Node implements Comparable<Node> {
        int vertex;
        int distance;

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

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

    static class Result {
        int distance;
        List<Integer> path;

        Result(int distance, List<Integer> path) {
            this.distance = distance;
            this.path = path;
        }
    }

    public static Map<Integer, List<Edge>> loadGraph(String filename) throws IOException {
        String text = Files.readString(Paths.get(filename));

        Pattern pattern = Pattern.compile("\\{(\\d+),\\s*(\\d+),\\s*(\\d+)\\}");
        Matcher matcher = pattern.matcher(text);

        Map<Integer, List<Edge>> graph = new HashMap<>();

        while (matcher.find()) {
            int u = Integer.parseInt(matcher.group(1));
            int v = Integer.parseInt(matcher.group(2));
            int w = Integer.parseInt(matcher.group(3));

            graph.putIfAbsent(u, new ArrayList<>());
            graph.putIfAbsent(v, new ArrayList<>());

            // Undirected graph
            graph.get(u).add(new Edge(v, w));
            graph.get(v).add(new Edge(u, w));
        }

        return graph;
    }

    public static Result dijkstra(Map<Integer, List<Edge>> graph, int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        Map<Integer, Integer> dist = new HashMap<>();
        Map<Integer, Integer> parent = new HashMap<>();
        Set<Integer> visited = new HashSet<>();

        pq.add(new Node(start, 0));
        dist.put(start, 0);
        parent.put(start, null);

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

            if (visited.contains(u)) {
                continue;
            }
            visited.add(u);

            if (u == end) {
                break;
            }

            List<Edge> neighbors = graph.getOrDefault(u, new ArrayList<>());
            for (Edge edge : neighbors) {
                int v = edge.to;
                int newDist = dist.get(u) + edge.weight;

                if (!dist.containsKey(v) || newDist < dist.get(v)) {
                    dist.put(v, newDist);
                    parent.put(v, u);
                    pq.add(new Node(v, newDist));
                }
            }
        }

        if (!dist.containsKey(end)) {
            return new Result(Integer.MAX_VALUE, new ArrayList<>());
        }

        List<Integer> path = new ArrayList<>();
        Integer current = end;
        while (current != null) {
            path.add(current);
            current = parent.get(current);
        }
        Collections.reverse(path);

        return new Result(dist.get(end), path);
    }

    public static void main(String[] args) {
        String filename = "graph.txt";

        try {
            Map<Integer, List<Edge>> graph = loadGraph(filename);
            Scanner scanner = new Scanner(System.in);

            System.out.println("Graph loaded.");
            System.out.println("Enter start and end vertices to find the shortest path.");
            System.out.println("Type -1 at any prompt to quit.\n");

            while (true) {
                System.out.print("Start vertex: ");
                int start = scanner.nextInt();
                if (start == -1) {
                    break;
                }

                System.out.print("End vertex: ");
                int end = scanner.nextInt();
                if (end == -1) {
                    break;
                }

                Result result = dijkstra(graph, start, end);

                if (result.distance == Integer.MAX_VALUE) {
                    System.out.println("No path found from " + start + " to " + end + ".\n");
                } else {
                    System.out.println("Shortest path length: " + result.distance);
                    System.out.println("Path: " + result.path + "\n");
                }
            }

            scanner.close();

        } catch (IOException e) {
            System.out.println("Error reading file: " + e.getMessage());
        } catch (InputMismatchException e) {
            System.out.println("Please enter valid integers.");
        }
    }
}