Single source to all destination shortest path problem

 

🔷 What is the Single Source All Destination Problem?

This is a classic shortest path problem in graph theory.

Goal: Find the shortest paths from a single source vertex to all other vertices in a  graph.

 

✅ Where is this used?

• GPS Navigation (shortest routes from a location to all others)

• Network routing (minimize packet delivery cost)

• Urban planning (shortest distances from a hub)

• Game AI pathfinding

---

🧠 Algorithms used:

• Dijkstra's Algorithm – For graphs with non-negative weights

• Bellman-Ford Algorithm – Works with negative weights

• Breadth-First Search (BFS) – Only for unweighted graphs

The Single Source to All Destination problem can be solved using Breadth-First Search (BFS) only if the graph is unweighted (or all edge weights are equal).

---

✅ Why BFS for Unweighted Graphs?

In an unweighted graph, the shortest path is the one with the least number of edges between nodes. BFS explores nodes level-by-level, so it naturally finds the shortest path in terms of edge count.

---

🔍 Problem Definition

Given: An unweighted graph and a source vertex s
Goal: Find the minimum number of edges (distance) from s to every other vertex.

---

🧠 BFS-Based Approach

Data Structures Needed:

• Queue: To do level-order traversal

• Visited[]: To mark visited nodes

• Distance[]: To store shortest distance from source

---

✅ Algorithm

1. Initialize visited[] and distance[] arrays
2. Enqueue the source node in a queue and mark it visited
3. While the queue is not empty:
   a. Dequeue a vertex u
   b. For each adjacent vertex v of u:
      i. If not visited:
         - Mark visited[v] = true
         - distance[v] = distance[u] + 1
         - Enqueue v

📘 Example: Unweighted Graph
Distances from A using BFS: 
 
A → A = 0 
 
A → B = 1 
 
A → C = 1 
 
A → D = 2 (A → B → D) 
 
A → E = 2 (A → C → E)
🧪 BFS Output
Node
Distance from A
A
    0
B        
    1
C
    1
D
    2
E
    2
✅ Time Complexity
O(V + E) where V = vertices and E = edges
🧾 Summary
Feature
BFS for Unweighted Graphs
Works on
    Unweighted or equally weighted graphs
Purpose
    Find shortest path from source to all
Output
    Shortest distance in edge count
Efficiency
    Linear time (O(V + E))

🧾C Program - Single Source All Destination
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX 100

// Adjacency list node
struct Node {
    int vertex;
    struct Node* next;
};

// Graph structure
struct Graph {
    int numVertices;
    struct Node** adjLists;
};

// Queue for BFS
struct Queue {
    int items[MAX];
    int front, rear;
};

// Create a node
struct Node* createNode(int v) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// Create a graph
struct Graph* createGraph(int vertices) {
    struct Graph* graph = malloc(sizeof(struct Graph));
    graph->numVertices = vertices;

    graph->adjLists = malloc(vertices * sizeof(struct Node*));

    for (int i = 0; i < vertices; i++)
        graph->adjLists[i] = NULL;

    return graph;
}

// Add edge (undirected)
void addEdge(struct Graph* graph, int src, int dest) {
    // Add edge from src to dest
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // Add edge from dest to src (undirected)
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// Create a queue
struct Queue* createQueue() {
    struct Queue* q = malloc(sizeof(struct Queue));
    q->front = -1;
    q->rear = -1;
    return q;
}

// Check if queue is empty
bool isEmpty(struct Queue* q) {
    return q->rear == -1;
}

// Enqueue
void enqueue(struct Queue* q, int value) {
    if (q->rear == MAX - 1)
        return;
    else {
        if (q->front == -1)
            q->front = 0;
        q->rear++;
        q->items[q->rear] = value;
    }
}

// Dequeue
int dequeue(struct Queue* q) {
    if (isEmpty(q))
        return -1;
    else {
        int item = q->items[q->front];
        q->front++;
        if (q->front > q->rear)
            q->front = q->rear = -1;
        return item;
    }
}

// BFS algorithm to compute shortest distance
void bfs(struct Graph* graph, int startVertex) {
    bool visited[MAX];
    int distance[MAX];

    for (int i = 0; i < graph->numVertices; i++) {
        visited[i] = false;
        distance[i] = -1;
    }

    struct Queue* q = createQueue();

    visited[startVertex] = true;
    distance[startVertex] = 0;
    enqueue(q, startVertex);

    while (!isEmpty(q)) {
        int currentVertex = dequeue(q);

        struct Node* temp = graph->adjLists[currentVertex];

        while (temp) {
            int adjVertex = temp->vertex;

            if (!visited[adjVertex]) {
                visited[adjVertex] = true;
                distance[adjVertex] = distance[currentVertex] + 1;
                enqueue(q, adjVertex);
            }
            temp = temp->next;
        }
    }

    // Print distances
    printf("Vertex\tDistance from Source %d\n", startVertex);
    for (int i = 0; i < graph->numVertices; i++)
        printf("%d\t%d\n", i, distance[i]);
}

// Main function
int main() {
    int vertices = 5;

    struct Graph* graph = createGraph(vertices);

    // Create the graph as per the example
    // 0-A, 1-B, 2-C, 3-D, 4-E
    addEdge(graph, 0, 1); // A-B
    addEdge(graph, 0, 2); // A-C
    addEdge(graph, 1, 3); // B-D
    addEdge(graph, 2, 4); // C-E

    int source = 0; // A as source

    bfs(graph, source);

    return 0;
}