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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a graph adjacency list using a vector of vectors.

DSA Rust

let mut graph: Vec<Vec<usize>> = vec![vec![]; [1]];

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

Anodes

Bedges

Cweights

Dpaths

Attempts:

3 left

💡 Hint

Common Mistakes

Using edges count instead of nodes count for adjacency list size.

We create an adjacency list with one vector per node, so the size must be the number of nodes.

2fill in blank

medium

Complete the code to add an edge from node u to node v in the adjacency list.

DSA Rust

graph[[1]].push(v);

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

Av

Bu

Cgraph

Dedges

Attempts:

3 left

💡 Hint

Common Mistakes

Using v as index instead of u.

We add v to the neighbors list of node u, so the index is u.

3fill in blank

hard

Fix the error in the code that tries to find the shortest path in a tree but uses a graph method.

DSA Rust

let mut dist = vec![usize::MAX; [1]];

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

Agraph

Bedges

Cnodes

Dpath

Attempts:

3 left

💡 Hint

Common Mistakes

Using edges count for distance vector size.

Distance vector size must match the number of nodes, not edges or other values.

4fill in blank

hard

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

DSA Rust

while let Some([1]) = queue.pop_front() {
    for &[2] in &graph[u] {
        // process neighbors
    }
}

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

Au

Bv

Cnode

Dedge

Attempts:

3 left

💡 Hint

Common Mistakes

Using the same variable name for both popped node and neighbor.

We pop node u from the queue and iterate over its neighbors v.

5fill in blank

hard

Fill all three blanks to complete the condition that updates distance and pushes neighbors in BFS.

DSA Rust

if dist[[1]] == usize::MAX {
    dist[[2]] = dist[u] + 1;
    queue.push_back([3]);
}

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

Av

Du

Attempts:

3 left

💡 Hint

Common Mistakes

Using u instead of v for distance or queue updates.

We check if neighbor v is unvisited, update its distance, and add v to the queue.

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 always have weighted edges, making shortest path trivial.

C. Because trees do not have nodes connected by edges.

D. Because shortest path algorithms only work on graphs with no edges.

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 consider 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:

   Graph complexity = shortest path problem [OK]

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

Common Mistakes:

• Thinking trees have cycles
• Assuming shortest path is trivial in trees
• Confusing edges with nodes

2. Which Rust code snippet correctly declares a graph using adjacency lists for shortest path problems?

easy

A. let graph: Vec> = vec![vec![]; n];

B. let graph: Vec<(usize, usize)> = vec![(0, 0); n];

C. let graph: Vec<usize> = vec![0; n];

D. let graph: HashMap = HashMap::new();

Solution

1. Step 1: Identify adjacency list structure

   An adjacency list for a weighted graph stores a vector of neighbors with weights, e.g., Vec>.

2. Step 2: Match Rust syntax

   let graph: Vec> = vec![vec![]; n]; correctly initializes a vector of vectors of tuples (neighbor, weight) with size n.

3. Final Answer:

   let graph: Vec> = vec![vec![]; n]; -> Option A

4. Quick Check:

   Adjacency list = Vec of Vec of (node, weight) [OK]

Hint: Adjacency list = Vec> in Rust [OK]

Common Mistakes:

• Using flat Vec instead of nested Vec
• Confusing HashMap with adjacency list
• Wrong tuple types for edges

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

medium

A. 5

B. 2

C. 6

D. 3

Solution

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

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

2. Step 2: Choose the minimum cost path

   Shortest path cost is 3 via 0->1->2.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Minimum path cost = 3 [OK]

Hint: Check all paths, pick smallest sum [OK]

Common Mistakes:

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

4. This Rust code tries to find shortest path but fails. What is the main bug?

let mut dist = vec![usize::MAX; n];
dist[0] = 0;
for i in 0..n {
  for &(v, w) in &graph[i] {
    if dist[i] + w < dist[v] {
      dist[v] = dist[i] + w;
    }
  }
}

medium

A. It uses usize::MAX which causes panic on addition.

B. It does not handle cycles properly, needs multiple iterations.

C. It initializes dist with zeros instead of max values.

D. It updates dist[v] without checking if v is visited.

Solution

1. Step 1: Analyze the loop structure

   The code runs only one pass over all edges, which is insufficient for graphs with cycles or longer paths.

2. Step 2: Understand shortest path algorithm requirements

   Algorithms like Bellman-Ford require multiple iterations to relax edges and handle cycles properly.

3. Final Answer:

   It does not handle cycles properly, needs multiple iterations. -> Option B

4. Quick Check:

   Single pass insufficient = bug [OK]

Hint: Shortest path needs repeated edge relaxation [OK]

Common Mistakes:

• Assuming one pass is enough
• Ignoring overflow risks
• Confusing initialization values

5. Given a graph with cycles and multiple edges, why can't shortest path be solved by treating it as a tree problem? Choose the best explanation.

medium

A. Because graphs have no root node, so shortest path algorithms don't apply.

B. Because trees always have equal edge weights, making shortest path trivial.

C. Because trees have no cycles, so shortest path in graphs requires handling cycles and multiple routes.

D. Because shortest path algorithms only work on disconnected graphs.

Solution

1. Step 1: Recall tree properties

   Trees are acyclic connected graphs with exactly one path between nodes.

2. Step 2: Understand graph complexity

   Graphs can have cycles and multiple paths, requiring algorithms that handle these complexities for shortest path.

3. Step 3: Connect to shortest path problem

   Shortest path in graphs must consider cycles and multiple routes, which trees do not have.

4. Final Answer:

   Because trees have no cycles, so shortest path in graphs requires handling cycles and multiple routes. -> Option C

5. Quick Check:

   Cycles and multiple paths = graph problem [OK]

Hint: Trees lack cycles; graphs need cycle handling [OK]

Common Mistakes:

• Assuming trees have cycles
• Thinking shortest path is trivial in graphs
• Confusing root node presence