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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to add an edge between two nodes in a graph represented as an adjacency list.

DSA Python

graph = {}
def add_edge(u, v):
    if u not in graph:
        graph[u] = []
    graph[u].append([1])

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

Av

Bu

C[v]

Dgraph

Attempts:

3 left

💡 Hint

Common Mistakes

Adding u instead of v to the adjacency list.

Adding a list [v] instead of just v.

Appending the whole graph instead of a node.

We add the node v to the adjacency list of u to represent an edge from u to v.

2fill in blank

medium

Complete the code to initialize the distance dictionary with infinity for all nodes in the graph.

DSA Python

distance = {node: [1] for node in graph}

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

ANone

B-1

Cfloat('inf')

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Setting distance to 0 for all nodes initially.

Using None which cannot be compared numerically.

Using negative values which don't make sense for distances.

We use float('inf') to represent an initially infinite distance to all nodes before running the shortest path algorithm.

3fill in blank

hard

Fix the error in the code that updates the distance to a neighbor node during shortest path calculation.

DSA Python

if distance[current] + weight < distance[[1]]:
    distance[neighbor] = distance[current] + weight

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

Acurrent

Bneighbor

Cweight

Ddistance

Attempts:

3 left

💡 Hint

Common Mistakes

Using current instead of neighbor in the distance dictionary.

Using weight as a key which is incorrect.

Using distance as a key which is invalid.

The distance to the neighbor node is updated if a shorter path is found through the current node.

4fill in blank

hard

Fill both blanks to complete the BFS traversal code that finds shortest paths in an unweighted graph.

DSA Python

from collections import deque
queue = deque([start])
distance = {start: 0}
while queue:
    current = queue.popleft()
    for neighbor in graph[current]:
        if neighbor not in distance:
            distance[neighbor] = distance[current] [1] 1
            queue.[2](neighbor)

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

A+

B-

Cappend

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Subtracting 1 instead of adding 1 to the distance.

Using pop instead of append to add neighbors to the queue.

We add 1 to the current distance to get the neighbor's distance and append the neighbor to the queue for BFS.

5fill in blank

hard

Fill all three blanks to complete the Dijkstra's algorithm step that updates distances and adds nodes to the priority queue.

DSA Python

import heapq
heap = []
heapq.heappush(heap, (0, start))
while heap:
    current_distance, current_node = heapq.heappop(heap)
    if current_distance > distance[current_node]:
        continue
    for neighbor, weight in graph[current_node]:
        distance_through_current = current_distance [1] weight
        if distance_through_current < distance[[2]]:
            distance[neighbor] = distance_through_current
            heapq.[3](heap, (distance_through_current, neighbor))

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

A+

Bneighbor

Cheappush

Dcurrent_node

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction instead of addition for distance calculation.

Using current_node instead of neighbor in distance comparison.

Using heappop instead of heappush to add elements.

We add the edge weight to the current distance, compare with the neighbor's distance, update if smaller, and push the neighbor with updated distance into the heap.

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

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

D. Because trees do not have nodes

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 C

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 nodes with edges

2. Which of the following is the correct Python syntax to represent a graph using an adjacency list?

easy

A. graph = {1: [2, 3], 2: [4], 3: [], 4: [1]}

B. graph = [1: [2, 3], 2: [4], 3: [], 4: [1]]

C. graph = (1: [2, 3], 2: [4], 3: [], 4: [1])

D. graph = {1 -> [2, 3], 2 -> [4], 3 -> [], 4 -> [1]}

Solution

1. Step 1: Identify valid Python data structures for adjacency lists

   Adjacency lists are best represented using dictionaries with keys as nodes and values as lists of neighbors.

2. Step 2: Check syntax correctness

   Only graph = {1: [2, 3], 2: [4], 3: [], 4: [1]} uses correct Python dictionary syntax with colons and square brackets.

3. Final Answer:

   graph = {1: [2, 3], 2: [4], 3: [], 4: [1]} -> Option A

4. Quick Check:

   Dictionary with colons and lists = D [OK]

Hint: Use curly braces and colons for dict, square brackets for lists [OK]

Common Mistakes:

• Using square brackets for dict instead of curly braces
• Using arrows (->) instead of colons
• Using parentheses instead of braces

3. What will be the output of the following code that tries to find the shortest path in a tree represented as a graph?

graph = {1: [2, 3], 2: [4], 3: [], 4: []}
visited = set()
def dfs(node):
    if node in visited:
        return
    visited.add(node)
    for neighbor in graph[node]:
        dfs(neighbor)
dfs(1)
print(sorted(visited))

medium

A. [1, 2, 3, 4]

B. [1, 2, 4]

C. [1, 3, 4]

D. [2, 3, 4]

Solution

1. Step 1: Trace the DFS traversal starting from node 1

   DFS visits 1, then 2, then 4, then backtracks and visits 3.

2. Step 2: Collect all visited nodes

   All nodes 1, 2, 3, and 4 are visited and added to the set.

3. Final Answer:

   [1, 2, 3, 4] -> Option A

4. Quick Check:

   DFS visits all connected nodes = C [OK]

Hint: DFS visits all reachable nodes from start [OK]

Common Mistakes:

• Forgetting to visit node 3
• Assuming DFS stops early
• Confusing visited set with path

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

graph = {1: [2, 3], 2: [4], 3: [4], 4: []}
visited = set()
def bfs(start):
    queue = [start]
    while queue:
        node = queue.pop()
        if node not in visited:
            visited.add(node)
            queue.extend(graph[node])
bfs(1)
print(sorted(visited))

medium

A. Missing return statement in bfs function

B. Not initializing visited before BFS

C. Extending queue with neighbors instead of appending one by one

D. Using pop() removes from the end, causing DFS behavior instead of BFS

Solution

1. Step 1: Understand queue operations for BFS

   BFS requires removing elements from the front (FIFO), but pop() removes from the end (LIFO).

2. Step 2: Identify effect of using pop() instead of pop(0)

   Using pop() causes the traversal to behave like DFS, not BFS, which affects shortest path correctness.

3. Final Answer:

   Using pop() removes from the end, causing DFS behavior instead of BFS -> Option D

4. Quick Check:

   pop() removes last = DFS, not BFS [OK]

Hint: BFS needs pop(0), pop() causes DFS [OK]

Common Mistakes:

• Confusing pop() with pop(0)
• Ignoring visited set initialization
• Thinking extend() is wrong here

5. Given a graph with cycles, why can't we use a tree-based shortest path algorithm directly, and what must we do instead?

hard

A. Because trees have weighted edges, we must convert the graph to a tree first

B. Because trees have no cycles, we must use graph algorithms like Dijkstra's with cycle checks

C. Because trees are always directed, we must ignore cycles in graphs

D. Because trees have only one node, we must split the graph into single nodes

Solution

1. Step 1: Understand difference between trees and graphs with cycles

   Trees have no cycles and unique paths, but graphs can have cycles and multiple paths.

2. Step 2: Explain why tree algorithms fail on graphs with cycles

   Tree algorithms assume no cycles; cycles cause infinite loops or incorrect paths if not handled.

3. Step 3: Identify correct approach for graphs with cycles

   Use graph algorithms like Dijkstra's that handle cycles and track visited nodes to find shortest paths.

4. Final Answer:

   Because trees have no cycles, we must use graph algorithms like Dijkstra's with cycle checks -> Option B

5. Quick Check:

   Graphs with cycles need special algorithms = B [OK]

Hint: Cycles need graph algorithms, not tree methods [OK]

Common Mistakes:

• Trying to convert graph to tree incorrectly
• Ignoring cycles cause infinite loops
• Assuming trees can represent all graphs