Shortest Path (Unweighted)

Problem Statement

Write a Java program that extends an unweighted undirected graph implementation to find the shortest path between two vertices using Breadth-First Search (BFS). The shortest path is the sequence of vertices with the minimum number of edges from the source to the target vertex. The program should use an adjacency list representation, return the path as a list of vertices, and test with various graphs and vertex pairs, including cases where a path exists, no path exists, and edge cases like empty or single-vertex graphs. You can visualize this as finding the fewest roads to travel between two cities in a network, where each road has the same length.

Input:

• An undirected unweighted graph represented by an adjacency list, with vertices as integers (0 to n-1).
• The number of vertices n, a list of edges (pairs of vertices), and two vertices source and target. Output: A list of integers representing the shortest path from source to target, or an empty list if no path exists, and a string representation of the graph’s adjacency list for clarity. Constraints:
• The number of vertices n is between 0 and 10^5.
• Edges are pairs of integers [u, v] where 0 ≤ u, v < n.
• Source and target are integers in [0, n-1].
• The graph is undirected (edge [u, v] implies [v, u]). Example:
• Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 4], [1, 4]], source = 0, target = 4
• Output: Path = [0, 1, 4], "Adjacency List: {0=[1], 1=[0, 2, 4], 2=[1, 3], 3=[2, 4], 4=[3, 1]}"
• Explanation: Shortest path from 0 to 4 is 0→1→4 (2 edges).
• Input: n = 5, edges = [[0, 1], [2, 3]], source = 0, target = 3
• Output: Path = [], "Adjacency List: {0=[1], 1=[0], 2=[3], 3=[2], 4=[]}"
• Explanation: No path exists from 0 to 3.
• Input: n = 0, edges = [], source = 0, target = 0
• Output: Path = [], "Adjacency List: {}"
• Explanation: Empty graph, no path exists.

Pseudocode

FUNCTION createGraph(n, edges)
    CREATE adjList as new HashMap
    FOR i from 0 to n-1
        SET adjList[i] to empty list
    ENDFOR
    FOR each edge [u, v] in edges
        ADD v to adjList[u]
        ADD u to adjList[v]
    ENDFOR
    RETURN adjList
ENDFUNCTION

FUNCTION shortestPath(adjList, n, source, target)
    IF n is 0 OR source >= n OR target >= n THEN
        RETURN empty list
    ENDIF
    CREATE visited as boolean array of size n, initialized to false
    CREATE parent as integer array of size n, initialized to -1
    CREATE queue as new Queue
    ADD source to queue
    SET visited[source] to true
    WHILE queue is not empty
        SET current to queue.dequeue
        IF current equals target THEN
            CREATE path as new list
            SET node to target
            WHILE node is not -1
                PREPEND node to path
                SET node to parent[node]
            ENDWHILE
            RETURN path
        ENDIF
        FOR each neighbor in adjList[current]
            IF NOT visited[neighbor] THEN
                SET visited[neighbor] to true
                SET parent[neighbor] to current
                ADD neighbor to queue
            ENDIF
        ENDFOR
    ENDWHILE
    RETURN empty list
ENDFUNCTION

FUNCTION toString(adjList)
    CREATE result as new StringBuilder
    APPEND "Adjacency List: {" to result
    FOR each vertex in adjList
        APPEND vertex and "=" and adjList[vertex] to result
        IF vertex is not last THEN
            APPEND ", " to result
        ENDIF
    ENDFOR
    APPEND "}" to result
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of (n, edges, source, target) pairs
    FOR each testCase in testCases
        PRINT test case details
        SET adjList to createGraph(testCase.n, testCase.edges)
        CALL shortestPath(adjList, testCase.n, testCase.source, testCase.target)
        PRINT path and graph using toString
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Reuse createGraph: a. Create a HashMap adjList mapping vertices to lists of neighbors. b. Initialize empty lists for vertices 0 to n-1. c. Add edges bidirectionally (u→v, v→u).
2. Define shortestPath: a. If n = 0 or source/target ≥ n, return empty list. b. Use BFS:
   • Initialize a queue with source, mark source as visited, set parent array.
   • Dequeue vertex, if it’s target, reconstruct path using parent array.
   • For each unvisited neighbor, mark visited, set parent, enqueue. c. If target not reached, return empty list.
3. Define toString: a. Convert adjacency list to a string, e.g., "{0=[1], 1=[0, 2], ...}".
4. In main, test with: a. A graph with a valid path. b. A graph with no path between vertices. c. An empty graph. d. A single-vertex graph.

Java Implementation

import java.util.*;

public class ShortestPathUnweighted {
    // Creates adjacency list representation of the graph
    private Map<Integer, List<Integer>> createGraph(int n, int[][] edges) {
        Map<Integer, List<Integer>> adjList = new HashMap<>();
        for (int i = 0; i < n; i++) {
            adjList.put(i, new ArrayList<>());
        }
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            adjList.get(u).add(v);
            adjList.get(v).add(u); // Undirected graph
        }
        return adjList;
    }

    // Finds shortest path from source to target using BFS
    public List<Integer> shortestPath(Map<Integer, List<Integer>> adjList, int n, int source, int target) {
        List<Integer> path = new ArrayList<>();
        if (n == 0 || source >= n || target >= n) {
            return path;
        }
        boolean[] visited = new boolean[n];
        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(source);
        visited[source] = true;

        while (!queue.isEmpty()) {
            int current = queue.poll();
            if (current == target) {
                // Reconstruct path
                int node = target;
                while (node != -1) {
                    path.add(0, node);
                    node = parent[node];
                }
                return path;
            }
            for (int neighbor : adjList.get(current)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    parent[neighbor] = current;
                    queue.offer(neighbor);
                }
            }
        }
        return path; // Empty if no path exists
    }

    // Converts graph to string (adjacency list)
    public String toString(Map<Integer, List<Integer>> adjList) {
        StringBuilder result = new StringBuilder("Adjacency List: {");
        List<Integer> vertices = new ArrayList<>(adjList.keySet());
        Collections.sort(vertices); // For consistent output
        for (int i = 0; i < vertices.size(); i++) {
            int vertex = vertices.get(i);
            result.append(vertex).append("=").append(adjList.get(vertex));
            if (i < vertices.size() - 1) {
                result.append(", ");
            }
        }
        result.append("}");
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        int n;
        int[][] edges;
        int source, target;

        TestCase(int n, int[][] edges, int source, int target) {
            this.n = n;
            this.edges = edges;
            this.source = source;
            this.target = target;
        }
    }

    // Main method to test shortest path
    public static void main(String[] args) {
        ShortestPathUnweighted pathFinder = new ShortestPathUnweighted();

        // Test cases
        TestCase[] testCases = {
            // Valid path: 0-1-4
            new TestCase(5, new int[][]{{0, 1}, {1, 2}, {2, 3}, {3, 4}, {1, 4}}, 0, 4),
            // No path: 0 and 3 disconnected
            new TestCase(5, new int[][]{{0, 1}, {2, 3}}, 0, 3),
            // Empty graph
            new TestCase(0, new int[][]{}, 0, 0),
            // Single vertex
            new TestCase(1, new int[][]{}, 0, 0)
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Vertices: " + testCases[i].n);
            System.out.println("Edges: " + Arrays.deepToString(testCases[i].edges));
            System.out.println("Source: " + testCases[i].source + ", Target: " + testCases[i].target);
            Map<Integer, List<Integer>> adjList = pathFinder.createGraph(testCases[i].n, testCases[i].edges);
            List<Integer> path = pathFinder.shortestPath(adjList, testCases[i].n, testCases[i].source, testCases[i].target);
            System.out.println("Path: " + path);
            System.out.println(pathFinder.toString(adjList) + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Vertices: 5
Edges: [[0, 1], [1, 2], [2, 3], [3, 4], [1, 4]]
Source: 0, Target: 4
Path: [0, 1, 4]
Adjacency List: {0=[1], 1=[0, 2, 4], 2=[1, 3], 3=[2, 4], 4=[3, 1]}

Test case 2:
Vertices: 5
Edges: [[0, 1], [2, 3]]
Source: 0, Target: 3
Path: []
Adjacency List: {0=[1], 1=[0], 2=[3], 3=[2], 4=[]}

Test case 3:
Vertices: 0
Edges: []
Source: 0, Target: 0
Path: []
Adjacency List: {}

Test case 4:
Vertices: 1
Edges: []
Source: 0, Target: 0
Path: [0]
Adjacency List: {0=[]}

Explanation:

• Test case 1: Shortest path from 0 to 4 is 0→1→4 (2 edges).
• Test case 2: No path exists from 0 to 3 (disconnected components).
• Test case 3: Empty graph, no path exists.
• Test case 4: Source and target are same (0), path is [0].

How It Works

• createGraph: Builds an adjacency list using a HashMap, adding undirected edges (u→v, v→u).
• shortestPath:
  • Returns empty list for invalid inputs (n = 0 or source/target ≥ n).
  • Uses BFS: enqueues source, marks visited, tracks parents.
  • If target reached, reconstructs path by backtracking through parent array.
  • Returns empty list if no path found.
• toString: Formats adjacency list as a string, sorting vertices for consistency.
• Example Trace (Test case 1):
  • BFS from 0: Enqueue 0, visit 1, enqueue 1.
  • Dequeue 1, visit 2, 4, enqueue 2, 4 (parent[2]=1, parent[4]=1).
  • Dequeue 2, visit 3, enqueue 3 (parent[3]=2).
  • Dequeue 4, target reached, reconstruct: 4→1→0, reverse to [0, 1, 4].
• Main Method: Tests valid path, no path, empty graph, and single vertex.

Complexity Analysis Table

Note:

• n is the number of vertices, e is the number of edges.
• Time complexity: O(n + e) for createGraph (initialize lists and add edges); O(n + e) for shortestPath (BFS visits each vertex and edge once); O(n log n + e) for toString (sorting vertices).
• Space complexity: O(n + e) for createGraph and toString (adjacency list); O(n) for shortestPath (visited array, parent array, queue).
• Worst case: O(n + e) time and space for dense graphs.

✅ Tip: Use BFS for finding the shortest path in unweighted graphs, as it explores vertices level by level. Store parent information to reconstruct the path efficiently.

⚠ Warning: Validate source and target vertices to ensure they are within the graph’s bounds. Handle cases where no path exists by returning an empty list.