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

BFS ensures shortest path in unweighted graphs.

dist[v] = dist[u] + 1 when visiting a neighbor.

Complexity: 

Adjacency Matrix → O(V²).
Adjacency List → O(V + E).

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>

#define MAX 20

#define INF 9999

int adj[MAX][MAX];   // adjacency matrix

int visited[MAX];    // visited array

int dist[MAX];       // distance array

int queue[MAX];      // queue for BFS

int front = 0, rear = -1;

// Enqueue

void enqueue(int v) {

    queue[++rear] = v;

}

// Dequeue

int dequeue() {

    return queue[front++];

}

// BFS traversal to compute shortest distances

void BFS(int n, int start) {

    int i, v;

    for (i = 0; i < n; i++) {

        visited[i] = 0;

        dist[i] = INF;

    }

    visited[start] = 1;

    dist[start] = 0;

    enqueue(start);

    while (front <= rear) {

        v = dequeue();

        for (i = 0; i < n; i++) {

            if (adj[v][i] == 1 && !visited[i]) {

                visited[i] = 1;

                dist[i] = dist[v] + 1;  // distance = parent distance + 1

                enqueue(i);

            }

        }

    }

}

int main() {

    int n, e, i, j, u, v, source;

    printf("Enter number of vertices: ");

    scanf("%d", &n);

    // Initialize adjacency matrix

    for (i = 0; i < n; i++)

        for (j = 0; j < n; j++)

            adj[i][j] = 0;

    printf("Enter number of edges: ");

    scanf("%d", &e);

    printf("Enter edges (u v) between 0 and %d:\n", n - 1);

    for (i = 0; i < e; i++) {

        scanf("%d %d", &u, &v);

        adj[u][v] = 1;

        adj[v][u] = 1; // for undirected graph

    }

    printf("Enter source vertex: ");

    scanf("%d", &source);

    BFS(n, source);

    printf("\nShortest distance from source %d:\n", source);

    for (i = 0; i < n; i++) {

        if (dist[i] == INF)

            printf("Vertex %d: Not reachable\n", i);

        else

            printf("Vertex %d: %d\n", i, dist[i]);

    }

    return 0;

}

Enter number of vertices: 5

Enter number of edges: 4

Enter edges (u v) between 0 and 4:

0 1

0 2

1 3

2 4

Enter source vertex: 0

Shortest distance from source 0:

Vertex 0: 0

Vertex 1: 1

Vertex 2: 1

Vertex 3: 2

Vertex 4: 2