Which reason best explains why shortest path problems require graph structures rather than just trees?
Think about whether trees can represent multiple routes between two points.
Trees are acyclic connected graphs, meaning there is exactly one path between any two nodes. Shortest path problems often require exploring multiple paths and cycles, which only graphs can represent.
Consider the following Java code snippet that tries to find shortest paths. What will be the output?
import java.util.*; class Graph { Map<Integer, List<Integer>> adj = new HashMap<>(); void addEdge(int u, int v) { adj.computeIfAbsent(u, k -> new ArrayList<>()).add(v); adj.computeIfAbsent(v, k -> new ArrayList<>()).add(u); } int shortestPath(int start, int end) { Queue<Integer> q = new LinkedList<>(); Set<Integer> visited = new HashSet<>(); Map<Integer, Integer> dist = new HashMap<>(); q.add(start); visited.add(start); dist.put(start, 0); while (!q.isEmpty()) { int node = q.poll(); if (node == end) return dist.get(node); for (int nei : adj.getOrDefault(node, Collections.emptyList())) { if (!visited.contains(nei)) { visited.add(nei); dist.put(nei, dist.get(node) + 1); q.add(nei); } } } return -1; } } public class Main { public static void main(String[] args) { Graph g = new Graph(); // Tree edges g.addEdge(1, 2); g.addEdge(1, 3); g.addEdge(2, 4); g.addEdge(2, 5); System.out.println(g.shortestPath(4, 5)); // Add cycle to make it a graph g.addEdge(4, 5); System.out.println(g.shortestPath(4, 5)); } }
Trace the shortest path before and after adding the cycle edge.
Initially, as a tree, the shortest path from 4 to 5 is 4 -> 2 -> 5 (length 2). After adding edge 4->5, direct edge reduces path length to 1.
Given this code snippet for shortest path, what is the main reason it might fail or give wrong results on graphs with cycles?
public int shortestPath(int start, int end, Map<Integer, List<Integer>> graph) { Set<Integer> visited = new HashSet<>(); Queue<Integer> queue = new LinkedList<>(); queue.add(start); int distance = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { int node = queue.poll(); if (node == end) return distance; for (int neighbor : graph.get(node)) { if (!visited.contains(neighbor)) { queue.add(neighbor); } } } distance++; } return -1; }
Look carefully if nodes are marked visited after being added to the queue.
The code never adds nodes to the visited set, so nodes in cycles get added repeatedly, causing infinite loops or wrong distances.
Which option contains the syntax error preventing this Java code from compiling?
public int shortestPath(int start, int end, Map<Integer, List<Integer>> graph) { Set<Integer> visited = new HashSet<>(); Queue<Integer> queue = new LinkedList<>(); queue.add(start); visited.add(start); int distance = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { int node = queue.poll(); if (node == end) return distance; for (int neighbor : graph.get(node)) { if (!visited.contains(neighbor)) { queue.add(neighbor); visited.add(neighbor); } } } distance++; } return -1; }
Look carefully at the end of each statement inside the loop.
The statement distance++ is missing a semicolon, causing a syntax error.
Which statement best explains why shortest path problems on weighted graphs require algorithms like Dijkstra's instead of simple BFS?
Think about how BFS measures distance and what happens when edges have different weights.
BFS treats all edges as having the same cost (weight 1). For weighted graphs where edges have different costs, BFS does not find the true shortest path. Dijkstra's algorithm accounts for varying weights to find the minimum total cost path.