Why Shortest Path Is a Graph Problem Not a Tree Problem in DSA C - Why This Pattern

Mental Model

Shortest path means finding the quickest way between two points when many routes exist. Trees have only one path between points, but graphs can have many paths and loops.

Analogy: Imagine a city map: a tree is like a single straight road with no turns, so only one way exists between places. A graph is like a city with many streets and intersections, so you can choose different routes to get somewhere faster.

Tree:
  1
 / \
2   3

Graph:
  1 -> 2
  ↑ ↘ ↓
  4 ← 3

Dry Run Walkthrough

Input: Graph with nodes 1, 2, 3, 4 and edges: 1->2, 2->3, 3->4, 4->1, 1->3; find shortest path from 1 to 4

Goal: Show why shortest path needs graph logic because multiple routes exist

Step 1: Start at node 1, check neighbors 2 and 3

Current: 1
Paths to explore: 2, 3

Why: We begin from start node and look at all possible next steps

Step 2: Move to node 2, check neighbors 3

Current: 2
Paths to explore: 3 (from 2), 3 (from 1)

Why: From node 2, we can go to node 3; node 3 is reachable from two paths

Step 3: Move to node 3, check neighbors 4

Current: 3
Paths to explore: 4

Why: From node 3, we can reach node 4, the destination

Step 4: Move to node 4, destination reached

Current: 4
Path found: 1 -> 3 -> 4 or 1 -> 2 -> 3 -> 4

Why: Multiple paths exist; shortest path is 1 -> 3 -> 4

Result:

1 -> 3 -> 4 is the shortest path
Graph state shows multiple routes and cycles

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_NODES 5

// Graph represented as adjacency matrix
int graph[MAX_NODES][MAX_NODES] = {
    {0, 0, 0, 0, 0}, // Node 0 unused
    {0, 0, 1, 1, 0}, // 1->2, 1->3
    {0, 0, 0, 1, 0}, // 2->3
    {0, 0, 0, 0, 1}, // 3->4
    {0, 1, 0, 0, 0}  // 4->1
};

// Simple queue for BFS
typedef struct {
    int items[MAX_NODES];
    int front, rear;
} Queue;

void enqueue(Queue* q, int val) {
    q->items[++q->rear] = val;
}

int dequeue(Queue* q) {
    return q->items[++q->front];
}

bool isEmpty(Queue* q) {
    return q->front == q->rear;
}

void shortestPath(int start, int end) {
    bool visited[MAX_NODES] = {false};
    int parent[MAX_NODES];
    for (int i = 0; i < MAX_NODES; i++) parent[i] = -1;

    Queue q = {.front = -1, .rear = -1};
    enqueue(&q, start);
    visited[start] = true;

    while (!isEmpty(&q)) {
        int current = dequeue(&q); // advance current node
        if (current == end) break; // stop if destination reached

        for (int i = 1; i < MAX_NODES; i++) {
            if (graph[current][i] && !visited[i]) {
                enqueue(&q, i); // enqueue neighbors
                visited[i] = true; // mark visited
                parent[i] = current; // track path
            }
        }
    }

    // Reconstruct path
    if (!visited[end]) {
        printf("No path found from %d to %d\n", start, end);
        return;
    }

    int path[MAX_NODES];
    int count = 0;
    for (int v = end; v != -1; v = parent[v]) {
        path[count++] = v; // build path backwards
    }

    printf("Shortest path from %d to %d: ", start, end);
    for (int i = count - 1; i >= 0; i--) {
        printf("%d", path[i]);
        if (i > 0) printf(" -> ");
    }
    printf("\n");
}

int main() {
    shortestPath(1, 4);
    return 0;
}

int current = dequeue(&q);

advance current node from queue to explore neighbors

if (current == end) break;

stop search when destination node is reached

if (graph[current][i] && !visited[i]) { enqueue(&q, i); visited[i] = true; parent[i] = current; }

enqueue unvisited neighbors and track their parent for path reconstruction

for (int v = end; v != -1; v = parent[v]) { path[count++] = v; }

reconstruct path by following parent links backwards from destination

Output

Shortest path from 1 to 4: 1 -> 3 -> 4

Complexity Analysis

Time: O(V + E) because BFS visits each node and edge once

Space: O(V) for visited array, queue, and parent tracking

vs Alternative: Unlike trees with one path, graphs need BFS or Dijkstra to handle multiple paths and cycles efficiently

Edge Cases

No path exists between start and end

The code prints 'No path found' message

DSA C

if (!visited[end]) { printf("No path found from %d to %d\n", start, end); return; }

Start and end are the same node

Shortest path is just the single node

DSA C

if (current == end) break;

When to Use This Pattern

When a problem asks for the shortest route between points with possible loops or multiple ways, recognize it as a graph problem needing BFS or Dijkstra, not a tree problem.

Common Mistakes

Mistake: Assuming only one path exists like in trees and not handling cycles
Fix: Use graph traversal algorithms like BFS that handle multiple paths and cycles

Summary

It shows why shortest path problems need graph algorithms because graphs can have many routes and loops.

Use graph algorithms when multiple paths or cycles exist between points.

The key insight is that trees have only one path between nodes, but graphs can have many, so shortest path needs graph logic.

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

C. Because shortest path algorithms only work on 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 A

4. Quick Check:

   Graphs allow multiple paths, trees do not [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 way to represent a graph for shortest path algorithms in C?

easy

A. Using an adjacency list with arrays of linked lists

B. Using a single integer variable

C. Using a string to store nodes

D. Using a stack only

Solution

1. Step 1: Identify common graph representations

   Graphs are commonly represented using adjacency lists or adjacency matrices for efficient traversal.

2. Step 2: Match representation to shortest path needs

   Adjacency lists with arrays of linked lists efficiently store neighbors for each node, suitable for shortest path algorithms.

3. Final Answer:

   Using an adjacency list with arrays of linked lists -> Option A

4. Quick Check:

   Adjacency list is standard graph representation [OK]

Hint: Use adjacency lists for graph representation in C [OK]

Common Mistakes:

• Using a single variable to represent graph
• Using strings instead of data structures
• Confusing stack with graph storage

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

int graph[3][3] = {
  {0, 1, 4},
  {1, 0, 2},
  {4, 2, 0}
};
// Find shortest path from node 0 to 2 using Dijkstra's algorithm
// What is the shortest distance?

medium

A. 6

B. 4

C. 5

D. 3

Solution

1. Step 1: Understand the graph matrix

   The matrix shows distances: 0->1=1, 0->2=4, 1->2=2.

2. Step 2: Calculate shortest path from 0 to 2

   Path 0->1->2 distance = 1 + 2 = 3, which is less than direct 0->2 distance 4.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   0->1->2 = 3 is shortest [OK]

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

Common Mistakes:

• Choosing direct edge without checking alternatives
• Adding edges incorrectly
• Ignoring intermediate nodes

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

int dist[5];
for(int i=0; i<=5; i++) {
  dist[i] = INT_MAX;
}

What is the bug?

medium

A. dist array is not initialized to zero

B. Loop goes out of array bounds causing undefined behavior

C. INT_MAX is not defined in C

D. Loop should start from 1 instead of 0

Solution

1. Step 1: Analyze the loop range and array size

   Array dist has size 5, valid indices are 0 to 4, but loop runs i=0 to 5 inclusive.

2. Step 2: Identify consequences of out-of-bounds access

   Accessing dist[5] is outside array bounds, causing undefined behavior or crash.

3. Final Answer:

   Loop goes out of array bounds causing undefined behavior -> Option B

4. Quick Check:

   Array index must be less than size [OK]

Hint: Loop index must be less than array size [OK]

Common Mistakes:

• Ignoring array bounds
• Confusing INT_MAX availability
• Changing loop start unnecessarily

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

hard

A. Because trees are slower than graphs for shortest path

B. Because trees require all edges to have the same weight

C. Because trees do not handle cycles or multiple paths, so shortest path may be missed

D. Because trees do not have nodes

Solution

1. Step 1: Understand tree limitations

   Trees have no cycles and only one unique path between nodes, so they cannot represent multiple paths or cycles.

2. Step 2: Analyze impact on shortest path

   In graphs with cycles and multiple paths, shortest path algorithms must consider all paths; trees cannot represent this complexity.

3. Final Answer:

   Because trees do not handle cycles or multiple paths, so shortest path may be missed -> Option C

4. Quick Check:

   Cycles and multiple paths need graphs, not trees [OK]

Hint: Cycles and multiple paths require graph structures [OK]

Common Mistakes:

• Assuming trees can represent cycles
• Thinking trees are faster always
• Confusing edge weights requirements