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

Practice - 5 Tasks

1fill in blank

easy

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

DSA C++

vector<int> graph[[1]];

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

A10

B1

C0

D5

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 or 0 as size causes out-of-bound errors.

The graph has 5 nodes, so the adjacency list array size should be 5.

2fill in blank

medium

Complete the code to add an edge from node 2 to node 3 in the graph.

DSA C++

graph[2].[1](3);

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

Aremove

Bpop_back

Cpush_back

Dinsert

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop_back or remove instead of push_back.

To add an edge, we use push_back to add node 3 to adjacency list of node 2.

3fill in blank

hard

Fix the error in the BFS loop to visit all neighbors of current node u.

DSA C++

for (int v : graph[[1]]) {
    if (!visited[v]) {
        visited[v] = true;
        q.push(v);
    }
}

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

Au

Bv

Cq

Dvisited

Attempts:

3 left

💡 Hint

Common Mistakes

Using graph[v] instead of graph[u].

We must iterate over neighbors of current node u, so use graph[u].

4fill in blank

hard

Fill both blanks to check if a node is already visited before adding to queue.

DSA C++

if (![1][[2]]) {
    visited[v] = true;
    q.push(v);
}

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

Avisited

Bv

Cu

Dq

Attempts:

3 left

💡 Hint

Common Mistakes

Checking visited[u] instead of visited[v].

We check if visited[v] is false before visiting node v.

5fill in blank

hard

Fill all three blanks to create a map of shortest distances from source node s.

DSA C++

vector<int> dist(n, [1]);
dist[[2]] = 0;
queue<int> q; q.push([3]);

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

A-1

Bs

C0

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing distances with 0 causes confusion between visited and unvisited.

Initialize distances with -1 (unvisited), set dist[s] = 0, and start BFS from s.

Practice

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

easy

A. Because shortest path algorithms only work on trees.

B. Because trees always have weighted edges, graphs do not.

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

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

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 require handling 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 D

4. Quick Check:

   Graphs allow multiple paths = A [OK]

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

Common Mistakes:

• Thinking trees can have cycles
• Assuming shortest path only applies to trees
• Confusing edge weights with graph structure

2. Which of the following is the correct way to represent a weighted graph in C++ for shortest path algorithms?

easy

A. vector>> graph; // stores node and weight pairs

B. vector graph; // only stores edges without weights

C. int graph[][]; // fixed size 2D array without weights

D. list<int> graph; // stores nodes only

Solution

1. Step 1: Identify data structure for weighted edges

   Weighted graphs need to store both the connected node and the edge weight, so pairs are used.

2. Step 2: Match with C++ syntax

   vector>> allows storing adjacency lists with (node, weight) pairs.

3. Final Answer:

   vector>> graph; // stores node and weight pairs -> Option A

4. Quick Check:

   Weighted edges need pairs = A [OK]

Hint: Use pairs to store node and weight in adjacency list [OK]

Common Mistakes:

• Using vector loses weight info
• Using fixed size arrays limits graph size
• Using list<int> cannot store edges properly

3. Consider the following C++ code snippet for a graph with edges and weights:

vector>> graph(3);
graph[0].push_back({1, 4});
graph[0].push_back({2, 1});
graph[1].push_back({2, 2});
graph[2].push_back({1, 1});

// What is the weight of the edge from node 0 to node 2?

medium

A. 4

B. 2

C. 1

D. No edge exists

Solution

1. Step 1: Read edges from node 0

   graph[0] has two edges: to node 1 with weight 4, and to node 2 with weight 1.

2. Step 2: Identify weight for edge 0 to 2

   The edge from node 0 to node 2 has weight 1 as per graph[0].push_back({2, 1}).

3. Final Answer:

   1 -> Option C

4. Quick Check:

   Edge 0->2 weight = 1 [OK]

Hint: Check adjacency list entries for node 0 [OK]

Common Mistakes:

• Confusing edge weights between nodes
• Assuming no edge exists from 0 to 2
• Mixing up node indices

4. The following code attempts to find the shortest path in a graph but has a bug:

vector>> graph(3);
graph[0].push_back({1, 5});
graph[1].push_back({2, 3});

int dist[3] = {INT_MAX, INT_MAX, INT_MAX};
dist[0] = 0;

for (int i = 0; i < 3; i++) {
  for (auto edge : graph[i]) {
    int v = edge.first;
    int w = edge.second;
    if (dist[i] + w < dist[v]) {
      dist[v] = dist[i] + w;
    }
  }
}

What is the main issue with this code?

medium

A. It does not initialize distances correctly.

B. It does not relax edges multiple times to find shortest paths.

C. It uses wrong data structure for graph.

D. It updates distances without checking for negative weights.

Solution

1. Step 1: Understand the relaxation process

   Shortest path algorithms like Bellman-Ford require multiple passes to relax edges and update distances.

2. Step 2: Analyze the loop structure

   The code only relaxes edges once in a single pass, which may not find shortest paths if multiple updates are needed.

3. Final Answer:

   It does not relax edges multiple times to find shortest paths. -> Option B

4. Quick Check:

   Single pass relaxation misses updates = D [OK]

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

Common Mistakes:

• Assuming one pass is enough
• Ignoring need for repeated relaxation
• Confusing initialization with relaxation

5. You have a graph with cycles and multiple paths between nodes. Why can't you use a tree-based shortest path algorithm here, and what approach should you use instead?

hard

A. Because trees have no cycles, use Dijkstra's algorithm on the graph instead.

B. Because trees have weighted edges, use BFS on the graph instead.

C. Because trees have cycles, use DFS on the graph instead.

D. Because trees are disconnected, use Prim's algorithm on the graph instead.

Solution

1. Step 1: Understand tree vs graph properties

   Trees have no cycles and exactly one path between nodes, so tree algorithms assume no alternative paths.

2. Step 2: Identify suitable shortest path algorithm for graphs

   Graphs with cycles and multiple paths require algorithms like Dijkstra's that handle weighted edges and cycles correctly.

3. Final Answer:

   Because trees have no cycles, use Dijkstra's algorithm on the graph instead. -> Option A

4. Quick Check:

   Cycles need graph algorithms like Dijkstra = B [OK]

Hint: Use Dijkstra for graphs with cycles, not tree algorithms [OK]

Common Mistakes:

• Using BFS for weighted graphs
• Confusing tree cycles with graph cycles
• Choosing Prim's which is for MST, not shortest path