---

⭐ All Pairs Shortest Paths (APSP)

Definition:
The All Pairs Shortest Paths (APSP) problem is to find the shortest path distances between every pair of vertices in a weighted graph:

[
\text{Compute } dist(u, v) \quad \forall ; u, v \in V
]

This is different from SSSP (Single Source Shortest Path), which finds shortest paths from only one source node.

---

⭐ Algorithms for APSP

There are three primary algorithms used for finding all-pairs shortest paths:

1. Floyd–Warshall Algorithm (Dynamic Programming)
2. Repeated Dijkstra Algorithm (Greedy)
3. Johnson’s Algorithm (Bellman–Ford + Dijkstra)

---

———————————————————–

1. FLOYD–WARSHALL ALGORITHM

———————————————————–

✔ Works for:

• Directed or Undirected graphs
• Negative edges allowed
• Detects negative-weight cycles

❌ Does NOT work if the graph has negative cycles.

---

⭐ Idea:

Dynamic programming method:
Try all vertices as intermediate nodes to improve existing shortest paths.

---

⭐ Algorithm:

Given dist[i][j] as shortest distance from i to j:

Recurrence Relation:

[
dist[i][j] = \min(dist[i][j],; dist[i][k] + dist[k][j])
]

Meaning:
Try using vertex k as an intermediate point in path i → j.

---

⭐ Pseudocode:

for k = 1 to V:
    for i = 1 to V:
        for j = 1 to V:
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

---

⭐ Time Complexity:

[
O(V^3)
]

---

⭐ Space Complexity:

[
O(V^2)
]

---

⭐ Key Features:

• Simple to implement
• Produces a distance matrix for all pairs
• Can detect negative cycles:
  • If dist[i][i] < 0 → negative cycle exists

---

———————————————————–

2. REPEATED DIJKSTRA

———————————————————–

✔ Works for:

• Non-negative edge weights
• Large sparse graphs
• Faster than Floyd–Warshall for sparse graphs

---

⭐ Idea:

Run Dijkstra’s algorithm from every vertex:

for each vertex u in V:
    run Dijkstra(u)

This gives shortest paths from u → all other vertices.

---

⭐ Time Complexity:

Using Min-Heap (Binary Heap):

[
O(V \cdot (E \log V)) = O(VE \log V)
]

Better for sparse graphs where E << V².

---

⭐ Not suitable for:

❌ Graphs with negative edges
(because Dijkstra fails with negative weights)

---

———————————————————–

3. JOHNSON’S ALGORITHM

———————————————————–

✔ Works for:

• Graphs with negative edges
• Graphs without negative cycles
• Large sparse graphs
• Combines benefits of Bellman–Ford + Dijkstra

---

⭐ Idea:

1. Add a new source node q connecting to all nodes with 0 weight.
2. Run Bellman–Ford from q → obtains reweighting function h(v)
3. Reweight all edges so that:
   • No negative edges remain
4. Run Dijkstra from each vertex

This gives correct APSP in good time.

---

⭐ Time Complexity:

[
O(V^2 \log V + VE)
]

---

⭐ Best When:

• Graph is large and sparse
• Contains negative edges

---

———————————————————–

⭐ Summary Table — APSP Algorithms

———————————————————–

Algorithm	Works With	Negative Edges	Negative Cycles	Time
Floyd–Warshall	Dense graphs	✔ Yes	✔ Detects	O(V³)
Repeated Dijkstra	Sparse graphs, non-negative	❌ No	No	O(VE log V)
Johnson’s Algorithm	Large sparse graphs	✔ Yes	✔ Detects	O(V² log V + VE)

---

———————————————————–

⭐ Applications of APSP

———————————————————–

• GPS navigation: compute all-to-all distance tables
• Routing tables in networks
• Social network analysis (shortest influence paths)
• Robot motion planning
• Airline route optimization
• Graph-based machine learning
• Cost/distance matrix generation

---

———————————————————–

⭐ Summary (One-line Revision)

———————————————————–

✔ Floyd–Warshall → Simple DP, handles negative edges, O(V³), good for dense graphs.
✔ Repeated Dijkstra → No negative weights, O(VE log V), good for sparse graphs.
✔ Johnson’s Algorithm → Handles negative edges, fast for large sparse graphs.

---