---

Single Source Shortest Path (SSSP)

The Single Source Shortest Path problem is:

Given a weighted graph ( G = (V, E) ), find the shortest path from a single start vertex ( s ) to all other vertices in the graph.

You want distance(s → v) for every vertex ( v ).

---

Why SSSP is Important?

Used in:

• GPS navigation
• Network routing
• Internet packet routing
• Supply chain optimization
• AI pathfinding
• Transportation systems

---

Types of SSSP Problems

1. Graphs with Non-negative Weights

Use Dijkstra’s Algorithm → Most common.

2. Graphs with Negative Weights

Use Bellman–Ford Algorithm.

3. DAG (Directed Acyclic Graph)

Use Topological Order Shortest Path.

4. All Pairs Shortest Path

Use Floyd–Warshall, but that’s not SSSP.

---

Main Algorithms for SSSP

We discuss the three main algorithms:

1. Dijkstra’s Algorithm — non-negative weights
2. Bellman–Ford Algorithm — handles negative weights
3. Shortest Paths in DAG — fastest for DAGs

---

1. Dijkstra’s Algorithm

Used For:

Graphs with non-negative weights (positive or zero).

Idea:

Greedy algorithm — always pick the closest unvisited vertex.

Data Structure:

Min-Heap / Priority Queue

Steps:

1. Set distance of source = 0, all others = ∞
2. Put source in min-heap
3. While heap is not empty:
   • Extract minimum distance vertex u
   • Relax all outgoing edges (u → v): if dist[u] + w(u,v) < dist[v]: dist[v] = dist[u] + w(u,v)
4. Continue until all nodes processed

Complexity:

Using Min-Heap:

[
O((V + E) \log V)
]

Cannot Handle:

❌ Negative weight edges
❌ Negative cycles

Because greedy choice breaks.

---

2. Bellman–Ford Algorithm

Used For:

Graphs with negative weights
(but no negative cycles)

Idea:

Dynamic Programming — relax all edges V–1 times.

Steps:

1. Initialize all distances: source = 0, others = ∞
2. Repeat V – 1 times:
   • Relax all edges (u, v)
3. Check for negative cycle:
   • If an edge can still be relaxed → negative cycle detected

Complexity:

[
O(VE)
]

Slow but powerful.

Can handle:

✔ Negative weights
✔ Detect negative cycles

Cannot handle:

❌ Graphs with negative cycle (no shortest path exists)

---

3. Shortest Path in DAG

Used For:

Directed Acyclic Graphs (DAGs)

Idea:

If the graph has no cycles, shortest path is easy.

Steps:

1. Compute Topological Order of vertices
2. Relax vertices in that topological order
3. Complexity → O(V + E) (fastest SSSP)

Supports:

✔ Negative weights
(but no negative cycles as DAG has no cycles)

---

Comparison (Very Important)

SSSP Type	Algorithm	Negative Weights	Negative Cycles	Time
Non-negative weights	Dijkstra	No	No	O(E log V)
Negative weights	Bellman–Ford	Yes	Detects	O(VE)
DAG	Topological DP	Yes	N/A	O(V + E)

---

Relaxation — Key Concept

Relaxing edge (u → v) means:

[
\text{If } dist[u] + w(u,v) < dist[v], \text{ update } dist[v].
]

Used in all SSSP algorithms.

---

Applications of SSSP

• Google Maps / GPS shortest route
• Network routing protocols (OSPF uses Dijkstra)
• Telecom networks
• Robotics path planning
• Logistics & supply chain optimization
• Social network influence spreading

---

Which Algorithm Should I Use?

Condition	Algorithm
All edges ≥ 0	Dijkstra
Some edges < 0	Bellman–Ford
Graph is DAG	Topological SSSP
Need fastest general SSSP	Dijkstra
Need negative cycle detection	Bellman–Ford

---

Example: Dijkstra (Short Conceptual Example)

Graph:
Edges with weights:

• A → B = 4
• A → C = 2
• C → B = 1
• B → D = 5
• C → D = 8

Start: A

Relaxation sequence:

1. dist[A] = 0
2. dist[C] = 2
3. dist[B] = 3
4. dist[D] = 8 (via B)

Shortest distances:

Node	Distance
A	0
B	3
C	2
D	8

---

Summary

Single Source Shortest Path (SSSP) identifies the shortest distance from a source vertex to all others.

Three main algorithms:

✔ Dijkstra (Non-negative weights)

O(E log V) → Fastest for most cases

✔ Bellman–Ford (Negative weights)

O(VE) → Slower but powerful

✔ DAG Shortest Path (Topological Order)

O(V + E) → Fastest when applicable

---