DijkstraUser.java

import java.util.*;

public class DijkstraUser {
    
    // Simple class to represent a connection between two nodes
    static class Connection {
        char from, to;
        int weight;
        
        Connection(char from, char to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }
    
    public static void main(String[] args) {
        // Step 1: Define your graph connections
        Connection[] connections = {
            new Connection('A','C',3), new Connection('G','B',1), new Connection('F','H',12),
            new Connection('C','F',9), new Connection('E','G',15), new Connection('G','I',10),
            new Connection('A','D',5), new Connection('B','E',3), new Connection('I','E',5),
            new Connection('C','D',2), new Connection('A','B',9), new Connection('F','G',4),
            new Connection('G','D',6), new Connection('H','I',6)
        };
        
        // Step 2: Get available nodes and take user input
        char[] availableNodes = getAllNodes(connections);
        Scanner scanner = new Scanner(System.in);
        
        System.out.println("=== DIJKSTRA'S SHORTEST PATH FINDER ===");
        System.out.print("Available nodes: ");
        for (int i = 0; i < availableNodes.length; i++) {
            System.out.print(availableNodes[i]);
            if (i < availableNodes.length - 1) System.out.print(", ");
        }
        System.out.println();
        
        char startNode;
        while (true) {
            System.out.print("Enter starting node (from above): ");
            String input = scanner.nextLine().trim().toUpperCase();
            
            if (input.length() == 1) {
                startNode = input.charAt(0);
                
                // Check if the node exists in the graph
                boolean nodeExists = false;
                for (char node : availableNodes) {
                    if (node == startNode) {
                        nodeExists = true;
                        break;
                    }
                }
                
                if (nodeExists) {
                    break;
                } else {
                    System.out.println("Error: Node '" + startNode + "' does not exist in the graph!");
                }
            } else {
                System.out.println("Error: Please enter a single character!");
            }
        }
        
        System.out.println("\nRunning Dijkstra's algorithm from node: " + startNode);
        
        // Step 3: Run Dijkstra
        dijkstra(connections, startNode);
        
        scanner.close();
    }
    
    public static void dijkstra(Connection[] connections, char start) {
        // Step 1: Find all unique nodes and store them in an array
        char[] allNodes = getAllNodes(connections);
        int numNodes = allNodes.length;
        
        // Step 2: Initialize arrays for distances, previous nodes, and visited status
        int[] distance = new int[numNodes];
        char[] previous = new char[numNodes];
        boolean[] visited = new boolean[numNodes];
        
        // Set all distances to infinity, except start node
        for (int i = 0; i < numNodes; i++) {
            distance[i] = Integer.MAX_VALUE;
            previous[i] = '-';
            visited[i] = false;
        }
        
        // Set start node distance to 0
        int startIndex = getNodeIndex(allNodes, start);
        distance[startIndex] = 0;
        
        // Step 3: Main algorithm loop
        for (int count = 0; count < numNodes; count++) {
            // Find the unvisited node with smallest distance
            int currentIndex = findClosestNode(distance, visited, numNodes);
            
            if (currentIndex == -1) break; // No more reachable nodes
            
            visited[currentIndex] = true;
            char current = allNodes[currentIndex];
            
            // Check all neighbors of current node
            for (Connection conn : connections) {
                char neighbor = 0;
                
                // Find if this connection involves current node
                if (conn.from == current) {
                    neighbor = conn.to;
                } else if (conn.to == current) {
                    neighbor = conn.from;
                } else {
                    continue; // This connection doesn't involve current node
                }
                
                int neighborIndex = getNodeIndex(allNodes, neighbor);
                
                // Skip if neighbor already visited
                if (visited[neighborIndex]) continue;
                
                // Calculate new distance through current node
                int newDistance = distance[currentIndex] + conn.weight;
                
                // If we found a shorter path, update it
                if (newDistance < distance[neighborIndex]) {
                    distance[neighborIndex] = newDistance;
                    previous[neighborIndex] = current;
                }
            }
        }
        
        // Step 4: Print results
        printResults(allNodes, distance, previous, start);
    }
    
    // Helper method: Get all unique nodes from connections
    private static char[] getAllNodes(Connection[] connections) {
        Set<Character> nodeSet = new HashSet<>();
        
        for (Connection conn : connections) {
            nodeSet.add(conn.from);
            nodeSet.add(conn.to);
        }
        
        // Convert to array and sort for consistent ordering
        char[] nodes = new char[nodeSet.size()];
        int i = 0;
        for (char node : nodeSet) {
            nodes[i++] = node;
        }
        Arrays.sort(nodes);
        
        return nodes;
    }
    
    // Helper method: Find the index of a node in the array
    private static int getNodeIndex(char[] nodes, char target) {
        for (int i = 0; i < nodes.length; i++) {
            if (nodes[i] == target) {
                return i;
            }
        }
        return -1; // Not found
    }
    
    // Helper method: Find the unvisited node with minimum distance
    private static int findClosestNode(int[] distance, boolean[] visited, int numNodes) {
        int minDistance = Integer.MAX_VALUE;
        int closestIndex = -1;
        
        for (int i = 0; i < numNodes; i++) {
            if (!visited[i] && distance[i] < minDistance) {
                minDistance = distance[i];
                closestIndex = i;
            }
        }
        return closestIndex;
    }
    
    // Helper method: Print the path from start to target
    private static void printPath(char[] allNodes, char[] previous, char target, char start) {
        if (target == start) {
            System.out.print(target);
            return;
        }
        
        int targetIndex = getNodeIndex(allNodes, target);
        char prev = previous[targetIndex];
        
        if (prev == '-') {
            System.out.print("-");
            return;
        }
        
        printPath(allNodes, previous, prev, start);
        System.out.print(" -> " + target);
    }
    
    // Helper method: Print all results in a nice format
    private static void printResults(char[] allNodes, int[] distance, char[] previous, char start) {
        System.out.println("\n=== DIJKSTRA'S ALGORITHM RESULTS ===");
        System.out.println("Starting from node: " + start);
        System.out.println("\nNode\tDistance\tPrevious\tPath from " + start);
        System.out.println("----\t--------\t--------\t---------");
        
        for (int i = 0; i < allNodes.length; i++) {
            char node = allNodes[i];
            int dist = distance[i];
            char prev = previous[i];
            
            System.out.printf("%c\t", node);
            
            if (dist == Integer.MAX_VALUE) {
                System.out.printf("∞\t\t-\t\tNo path\n");
            } else {
                System.out.printf("%d\t\t%c\t\t", dist, prev);
                printPath(allNodes, previous, node, start);
                System.out.println();
            }
        }
    }
}