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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create an adjacency list for a graph.

DSA Javascript

const graph = {};
graph['A'] = [1];

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

A('B', 'C')

B{'B', 'C'}

C'B', 'C'

D['B', 'C']

Attempts:

3 left

💡 Hint

Common Mistakes

Using curly braces {} which create an object, not an array.

Using parentheses () which create a tuple in some languages but not in JavaScript.

Listing neighbors without brackets, which is invalid syntax.

The adjacency list for node 'A' should be an array of connected nodes, so ['B', 'C'] is correct.

2fill in blank

medium

Complete the code to add a new edge from node 'B' to node 'D'.

DSA Javascript

graph['B'].[1]('D');

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

Aadd

Bappend

Cpush

Dinsert

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'append' which is a Python method, not JavaScript.

Using 'add' which is for sets, not arrays.

Using 'insert' which is not a JavaScript array method.

In JavaScript arrays, the method to add an element at the end is push.

3fill in blank

hard

Fix the error in the function to find neighbors of a node.

DSA Javascript

function getNeighbors(node) {
  return graph[[1]];
}

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

Anode

B'node'

Cgraph

Dneighbors

Attempts:

3 left

💡 Hint

Common Mistakes

Using quotes around node, which accesses the wrong key.

Using 'graph' which is the whole graph, not a key.

Using 'neighbors' which is undefined.

We want to access the neighbors of the given node, so use the variable node without quotes.

4fill in blank

hard

Fill both blanks to check if a node has neighbors and return them.

DSA Javascript

function safeGetNeighbors(node) {
  if (graph[[1]] [2] undefined) {
    return graph[node];
  } else {
    return [];
  }
}

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

Anode

B!==

C==

Dgraph

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'graph' instead of 'node' as the key.

Using '==' instead of '!==', which reverses the logic.

We check if graph[node] is not equal to undefined to confirm neighbors exist.

5fill in blank

hard

Fill all three blanks to create a function that finds the shortest path length using BFS.

DSA Javascript

function shortestPathLength(start, end) {
  const queue = [[start, 0]];
  const visited = new Set([start]);
  while (queue.length > 0) {
    const [node, distance] = queue.shift();
    if (node === [1]) return distance;
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.[2]([neighbor, distance [3] 1]);
      }
    }
  }
  return -1;
}

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

Aend

Bpush

C+

Dstart

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing to 'start' instead of 'end'.

Using 'pop' instead of 'push' on the queue.

Using '-' instead of '+' to update distance.

We compare node to end, add neighbors to the queue with push, and increase distance by 1 using +.

Practice

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

easy

A. Because trees do not have nodes

B. Because trees always have equal path lengths

C. Because shortest path algorithms only work on trees

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 = shortest path 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 nodes with edges

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

easy

A. const graph = { A: ['B', 'C'], B: ['A'], C: ['A'] };

B. const graph = ['A', 'B', 'C'];

C. const graph = { A: 1, B: 2, C: 3 };

D. const graph = [ ['A', 'B'], ['B', 'C'] ];

Solution

1. Step 1: Identify graph representation formats

   Graphs are often represented as adjacency lists, where each node maps to an array of connected nodes.

2. Step 2: Match the correct JavaScript syntax

   const graph = { A: ['B', 'C'], B: ['A'], C: ['A'] }; uses an object with keys as nodes and arrays as neighbors, which is a valid adjacency list.

3. Final Answer:

   const graph = { A: ['B', 'C'], B: ['A'], C: ['A'] }; -> Option A

4. Quick Check:

   Adjacency list = object with arrays [OK]

Hint: Adjacency list uses object keys with neighbor arrays [OK]

Common Mistakes:

• Using arrays without keys for adjacency
• Confusing node labels with values
• Using arrays of nodes without connections

3. Consider the following graph represented as an adjacency list:

const graph = { A: ['B', 'C'], B: ['A', 'D'], C: ['A', 'D'], D: ['B', 'C'] };

Using a shortest path algorithm from node 'A' to 'D', what is the length of the shortest path?

medium

A. 2

B. 3

C. 1

D. 4

Solution

1. Step 1: List all paths from 'A' to 'D'

   Possible paths: A->B->D and A->C->D, both have 2 edges.

2. Step 2: Determine shortest path length

   Both paths have length 2, so shortest path length is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Shortest path edges count = 2 [OK]

Hint: Count edges in shortest route from start to end [OK]

Common Mistakes:

• Counting nodes instead of edges
• Ignoring multiple paths
• Assuming direct edge exists

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

function shortestPath(graph, start, end) {
  let queue = [start];
  let visited = new Set();
  let distance = {};
  distance[start] = 0;

  while (queue.length > 0) {
    let node = queue.shift();
    if (node === end) return distance[node];
    for (let neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        distance[neighbor] = distance[node] + 1;
        queue.push(neighbor);
      }
    }
  }
  return -1;
}

What is the main bug in this code?

medium

A. The distance object is not updated

B. The queue is not initialized correctly

C. The visited set is never updated for the start node

D. The function does not return anything

Solution

1. Step 1: Check visited set usage

   The start node is added to the queue but not marked visited initially, so it may be revisited.

2. Step 2: Understand BFS behavior

   Without marking start visited, neighbors may be processed multiple times, causing incorrect distances or infinite loops.

3. Final Answer:

   The visited set is never updated for the start node -> Option C

4. Quick Check:

   Start node must be visited first [OK]

Hint: Always mark start node visited before BFS loop [OK]

Common Mistakes:

• Forgetting to mark start visited
• Assuming queue initialization fixes visited
• Ignoring visited set usage

5. You have a graph with weighted edges, and some edges form cycles. Why can't you use a simple tree shortest path algorithm here, and which algorithm is suitable instead?

hard

A. Because trees have weighted edges; use Prim's algorithm for shortest path

B. Because trees have no cycles; use Dijkstra's algorithm for weighted graphs with cycles

C. Because trees allow multiple paths; use DFS for weighted graphs

D. Because trees have cycles; use BFS for weighted graphs

Solution

1. Step 1: Understand tree vs graph with cycles and weights

   Trees have no cycles and unweighted edges, so simple shortest path methods for trees don't apply to weighted graphs with cycles.

2. Step 2: Identify suitable algorithm for weighted graphs with cycles

   Dijkstra's algorithm handles weighted edges and cycles correctly to find shortest paths.

3. Final Answer:

   Because trees have no cycles; use Dijkstra's algorithm for weighted graphs with cycles -> Option B

4. Quick Check:

   Weighted graph + cycles = Dijkstra's algorithm [OK]

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

Common Mistakes:

• Using BFS for weighted graphs
• Confusing Prim's algorithm with shortest path
• Ignoring cycles in graph