Why Shortest Path Is a Graph Problem Not a Tree Problem in DSA Java - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the adjacency list for a graph with 5 nodes.

DSA Java

List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < [1]; i++) {
    graph.add(new ArrayList<>());
}

Drag options to blanks, or click blank then click option'

A5

B4

C6

D3

Attempts:

3 left

💡 Hint

Common Mistakes

Using the wrong number of nodes in the loop.

The graph has 5 nodes, so we initialize the adjacency list with 5 empty lists.

2fill in blank

medium

Complete the code to add an edge from node 0 to node 1 in the graph.

DSA Java

graph.get(0).[1](1);

Drag options to blanks, or click blank then click option'

Aadd

Bremove

Cset

Dclear

Attempts:

3 left

💡 Hint

Common Mistakes

Using remove or clear instead of add.

To add an edge, we use the add method on the adjacency list of node 0.

3fill in blank

hard

Fix the error in the code to correctly check if a node has been visited.

DSA Java

if (!visited[[1]]) {
    // process node
}

Drag options to blanks, or click blank then click option'

Aedges

Bvisited

Cgraph

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using the visited array itself as an index.

The visited array is indexed by the node number, so we check visited[node].

4fill in blank

hard

Fill both blanks to complete the BFS loop that finds the shortest path in a graph.

DSA Java

while (!queue.[1]()) {
    int current = queue.[2]();
    // process current node
}

Drag options to blanks, or click blank then click option'

AisEmpty

Bpoll

Cpeek

Dremove

Attempts:

3 left

💡 Hint

Common Mistakes

Using peek() which does not remove the element.

We check if the queue is empty with isEmpty(), and remove the front element with poll() in BFS.

5fill in blank

hard

Fill all three blanks to update the distance array during BFS traversal.

DSA Java

if (!visited[neighbor]) {
    visited[neighbor] = true;
    distance[neighbor] = distance[[1]] + [2];
    queue.[3](neighbor);
}

Drag options to blanks, or click blank then click option'

Acurrent

B1

Cadd

Doffer

Attempts:

3 left

💡 Hint

Common Mistakes

Using add() instead of offer(), or wrong distance calculation.

Distance to neighbor is distance[current] + 1, and we add neighbor to the queue with offer().

Practice

1. Why is finding the shortest path usually considered a graph problem rather than a tree problem?

easy

A. Because graphs can have cycles and multiple paths between nodes, unlike trees

B. Because trees do not have nodes

C. Because shortest path algorithms only work on trees

D. Because trees always have negative edge weights

Solution

1. Step 1: Understand the structure of trees and graphs

   Trees are a special type of graph with no cycles and exactly one path between any two nodes.

2. Step 2: Analyze shortest path requirements

   Shortest path problems need to handle multiple paths and cycles, which only general graphs can have.

3. Final Answer:

   Because graphs can have cycles and multiple paths between nodes, unlike trees -> Option A

4. Quick Check:

   Graphs allow multiple paths = Shortest path is a graph problem [OK]

Hint: Shortest path needs multiple paths; trees have only one [OK]

Common Mistakes:

• Thinking trees have cycles
• Assuming shortest path only applies to trees
• Confusing node existence in trees

2. Which of the following Java code snippets correctly declares a graph using adjacency lists?

easy

A. Map graph = new HashMap<>();

B. int graph = new int[5][5];

C. List graph = new ArrayList<>();

D. List<Integer> graph = new LinkedList<>();

Solution

1. Step 1: Identify adjacency list structure

   An adjacency list for a graph is a list of lists, where each inner list holds neighbors of a node.

2. Step 2: Match code to adjacency list

   List graph = new ArrayList<>(); declares a list of lists of integers, suitable for adjacency lists.

3. Final Answer:

   List graph = new ArrayList<>(); -> Option C

4. Quick Check:

   Adjacency list = List of Lists [OK]

Hint: Adjacency list = List of Lists in Java [OK]

Common Mistakes:

• Using 2D array for adjacency list
• Using Map with single Integer value
• Using single list for graph

3. Consider the following Java code snippet for a graph with edges: 0->1 (weight 2), 0->2 (weight 4), 1->2 (weight 1). What is the shortest path distance from node 0 to node 2 using Dijkstra's algorithm?

medium

A. 4

B. 3

C. 2

D. 5

Solution

1. Step 1: List all paths from 0 to 2

   Paths: 0->2 with cost 4, 0->1->2 with cost 2+1=3.

2. Step 2: Choose the minimum cost path

   Between 4 and 3, the shortest path cost is 3 via 0->1->2.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Shortest path cost = 3 [OK]

Hint: Check all paths, pick minimum sum of weights [OK]

Common Mistakes:

• Choosing direct edge without checking alternate paths
• Adding weights incorrectly
• Ignoring intermediate nodes

4. The following Java code attempts to find the shortest path in a graph but has a bug. What is the error?

int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[source] = 0;
for (Edge e : edges) {
  if (dist[e.from] + e.weight < dist[e.to]) {
    dist[e.to] = dist[e.from] + e.weight;
  }
}

medium

A. The code misses relaxing edges multiple times

B. The code does not initialize the distance array

C. The code does not handle negative weight edges

D. The code uses wrong comparison operator

Solution

1. Step 1: Understand the relaxation process

   Relaxation must be repeated multiple times to propagate shortest distances correctly.

2. Step 2: Identify loop count issue

   The code runs the relaxation only once over all edges, which is insufficient for graphs with multiple edges.

3. Final Answer:

   The code misses relaxing edges multiple times -> Option A

4. Quick Check:

   Relax edges repeatedly = Correct shortest path [OK]

Hint: Relax edges multiple times for shortest path [OK]

Common Mistakes:

• Assuming one pass is enough
• Confusing initialization with relaxation
• Ignoring edge weights

5. Given a graph with cycles and multiple paths, why can't we use a tree-based shortest path algorithm like DFS to find the shortest path reliably?

hard

A. Because DFS requires graphs to be acyclic

B. Because DFS always finds the longest path

C. Because trees do not have nodes

D. Because DFS does not consider edge weights and may miss shorter paths

Solution

1. Step 1: Understand DFS behavior

   DFS explores paths deeply without considering edge weights, so it may not find the shortest weighted path.

2. Step 2: Compare with shortest path needs

   Shortest path algorithms must consider weights and multiple paths, which DFS does not handle properly.

3. Final Answer:

   Because DFS does not consider edge weights and may miss shorter paths -> Option D

4. Quick Check:

   DFS ignores weights = Not reliable for shortest path [OK]

Hint: DFS ignores weights; shortest path needs weights [OK]

Common Mistakes:

• Thinking DFS finds shortest path by default
• Confusing DFS with BFS
• Assuming trees have cycles