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.