DSA Shortest Path

DSA Shortest Path – Complete Beginner Guide

(Concept • Algorithms • When to Use What • Examples • Code • Complexity)

Shortest Path algorithms help find the minimum distance / cost from one node to another in a graph.
This is a core DSA topic and a favorite in interviews.

1️⃣ What is the Shortest Path Problem?

Given:

A graph (directed / undirected)
A source vertex

Find:

The minimum distance from the source to all other vertices
(or to a specific destination)

2️⃣ Types of Shortest Path Problems

Case	Example
Single Source → All	Google Maps from one location
Single Source → One	Shortest route A → B
All Pairs	Network routing tables

3️⃣ Which Shortest Path Algorithm to Use? (VERY IMPORTANT)

Graph Type	Algorithm
Unweighted Graph	BFS
Weighted (No negative)	Dijkstra
Weighted (Negative edges)	Bellman-Ford
All-Pairs Shortest Path	Floyd–Warshall
DAG	Topological Sort + Relaxation

PART 1: Shortest Path in Unweighted Graph (BFS)

4️⃣ BFS Shortest Path

Why BFS?

BFS explores level by level
First time reaching a node = shortest path

Algorithm (BFS)

Initialize distance array with ∞
Distance[source] = 0
Use queue
For each neighbor:
- If unvisited, update distance

C++ Code (Unweighted Graph)

#include <queue>
#include <vector>
#include <iostream>
using namespace std;

void shortestPathBFS(int src, vector<int> adj[], int V) {
    vector<int> dist(V, -1);
    queue<int> q;

    dist[src] = 0;
    q.push(src);

    while(!q.empty()) {
        int node = q.front();
        q.pop();

        for(int x : adj[node]) {
            if(dist[x] == -1) {
                dist[x] = dist[node] + 1;
                q.push(x);
            }
        }
    }

    for(int i = 0; i < V; i++)
        cout << "Distance from " << src << " to " << i << " = " << dist[i] << endl;
}

#include <queue>

#include <vector>

#include <iostream>

using namespace std;

void shortestPathBFS(int src, vector<int> adj[], int V) {

vector<int> dist(V, -1);

queue<int> q;

dist[src] = 0;

q.push(src);

while(!q.empty()) {

int node = q.front();

q.pop();

for(int x : adj[node]) {

if(dist[x] == -1) {

dist[x] = dist[node] + 1;

q.push(x);

}

for(int i = 0; i < V; i++)

cout << "Distance from " << src << " to " << i << " = " << dist[i] << endl;

}

Time Complexity

PART 2: Shortest Path in Weighted Graph (Dijkstra)

5️⃣ Dijkstra’s Algorithm

Conditions

✔ Graph with non-negative weights
❌ Does NOT work with negative edges

Core Idea

Greedy algorithm
Always picks closest unvisited node
Uses priority queue (min-heap)

Steps

Distance[source] = 0
Push (distance, node) into min-heap
Relax edges
Repeat until heap empty

C++ Code (Dijkstra)

#include <queue>
#include <vector>
using namespace std;

void dijkstra(int src, vector<pair<int,int>> adj[], int V) {
    vector<int> dist(V, 1e9);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;

    dist[src] = 0;
    pq.push({0, src});

    while(!pq.empty()) {
        int node = pq.top().second;
        int d = pq.top().first;
        pq.pop();

        if(d > dist[node]) continue;

        for(auto it : adj[node]) {
            int next = it.first;
            int weight = it.second;

            if(dist[node] + weight < dist[next]) {
                dist[next] = dist[node] + weight;
                pq.push({dist[next], next});
            }
        }
    }
}

#include <queue>

#include <vector>

using namespace std;

void dijkstra(int src, vector<pair<int,int>> adj[], int V) {

vector<int> dist(V, 1e9);

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;

dist[src] = 0;

pq.push({0, src});

while(!pq.empty()) {

int node = pq.top().second;

int d = pq.top().first;

pq.pop();

if(d > dist[node]) continue;

for(auto it : adj[node]) {

int next = it.first;

int weight = it.second;

if(dist[node] + weight < dist[next]) {

dist[next] = dist[node] + weight;

pq.push({dist[next], next});

}

Time Complexity

PART 3: Shortest Path with Negative Weights

6️⃣ Bellman–Ford Algorithm

Features

✔ Handles negative edges
✔ Detects negative weight cycles
❌ Slower than Dijkstra

Idea

Relax all edges V−1 times
One more pass to check negative cycle

Time Complexity

7️⃣ All-Pairs Shortest Path

Floyd–Warshall Algorithm

Dynamic Programming
Finds shortest paths between every pair

Complexity:

Used when graph is small.

8️⃣ Shortest Path in DAG

For Directed Acyclic Graph:

Topological sort
Relax edges in topo order

Complexity:

9️⃣ Comparison Summary

Algorithm	Weights	Cycles	Complexity
BFS	No	Yes	O(V+E)
Dijkstra	+ve only	Yes	O(E log V)
Bellman-Ford	Any	Yes	O(VE)
Floyd-Warshall	Any	Yes	O(V³)

🔟 Real-Life Applications

✔ Google Maps & GPS
✔ Network routing
✔ Game AI pathfinding
✔ Social networks
✔ Logistics & supply chain

Interview Questions (Shortest Path)

Q1. Why BFS gives shortest path in unweighted graph?
👉 Level-wise traversal

Q2. Why Dijkstra fails with negative weights?
👉 Greedy assumption breaks

Q3. Which algorithm detects negative cycle?
👉 Bellman-Ford

Final Summary

✔ Shortest path finds minimum distance
✔ Algorithm depends on graph type
✔ BFS → Unweighted
✔ Dijkstra → Positive weights
✔ Bellman-Ford → Negative weights
✔ Extremely important for DSA interviews

DSA Shortest Path