Why Shortest Path Is a Graph Problem Not a Tree Problem in DSA C - See It Work

Why Shortest Path Is a Graph Problem Not a Tree Problem

📖 Scenario: Imagine you are planning a trip in a city. The city map has many roads connecting different places. You want to find the shortest way to get from your home to a park. This is like finding the shortest path in a network of roads.Some maps look like trees, where there is only one way to reach each place. But real city maps have many roads connecting places in different ways, making them graphs, not trees.

🎯 Goal: You will create a simple map using a graph data structure and understand why shortest path problems need graphs, not trees. You will see how multiple paths between places affect finding the shortest route.

📋 What You'll Learn

Create a graph using adjacency lists to represent places and roads

Add a variable to track the number of places (nodes)

Write a function to find the shortest path using a simple breadth-first search (BFS)

Print the shortest path distance from a start place to all other places

💡 Why This Matters

🌍 Real World

Finding shortest routes in maps, network routing, social network connections, and many real-life navigation problems.

💼 Career

Understanding graph structures and shortest path algorithms is essential for software engineers working in fields like GIS, networking, and data science.

1

Create the graph data structure

Create an adjacency list graph with 4 places (nodes) named 0, 1, 2, 3. Use an array of linked lists called graph to store neighbors for each node.

DSA C

# Define the graph with 4 nodes using adjacency lists
// Your code here

Hint

Use a struct for linked list nodes and an array of pointers for the graph.

2

Add edges to the graph

Add edges to the graph to connect nodes: 0-1, 0-2, 1-2, and 2-3. Write a function add_edge that adds an edge from one node to another. Use it to build the graph.

DSA C

#include 
#include 

#define NODES 4

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* graph[NODES] = {NULL, NULL, NULL, NULL};

// Write add_edge function here

int main() {
    // Use add_edge to connect 0-1, 0-2, 1-2, 2-3
    // Your code here
    return 0;
}

Hint

Remember to add edges only one way for now (directed). Use malloc to create new nodes.

3

Implement BFS to find shortest paths

Write a function bfs that takes a start node and prints the shortest distance to all other nodes using breadth-first search. Use an array distance to store distances and initialize them to -1. Set distance to 0 for the start node.

DSA C

#include 
#include 

#define NODES 4

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* graph[NODES] = {NULL, NULL, NULL, NULL};

void add_edge(int src, int dest) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph[src];
    graph[src] = newNode;
}

void bfs(int start) {
    // Your code here
}

int main() {
    add_edge(0, 1);
    add_edge(0, 2);
    add_edge(1, 2);
    add_edge(2, 3);
    bfs(0);
    return 0;
}

Hint

Use a queue to explore nodes level by level. Update distances when visiting nodes first time.

4

Print shortest path distances

Run the program and observe the printed shortest distances from node 0 to all other nodes. The output shows why shortest path needs graphs, not trees, because multiple paths exist.

DSA C

#include 
#include 

// Run the program to print shortest distances
// Your code here

Hint

Check the console output after running the program.