Shortest Path Algorithms

Finding the shortest path between two points is one of computing's most practical problems. GPS navigation, network routing, game AI pathfinding, and social network analysis all rely on shortest path algorithms. This article covers the four essential algorithms: Dijkstra's for non-negative weights, Bellman-Ford for negative weights, Floyd-Warshall for all pairs, and A* for heuristic-guided search.

📋 At a Glance

Algorithm	Time	Space	Handles Negative	Best For
Dijkstra (binary heap)	O((V+E) log V)	O(V)	No	Single source, non-negative
Bellman-Ford	O(VE)	O(V)	Yes (detects cycles)	Negative weights
Floyd-Warshall	O(V³)	O(V²)	Yes (detects cycles)	All pairs, dense graphs
A*	O(E) best, O(V²) worst	O(V)	No	Single pair with heuristic

🎯 What You'll Learn

After reading this article, you will be able to:

Implement Dijkstra's algorithm with proper priority queue usage
Handle negative weights using Bellman-Ford
Compute all-pairs shortest paths with Floyd-Warshall
Apply A search* with admissible heuristics
Detect negative cycles that make shortest path undefined
Choose the right algorithm based on graph characteristics

🔥 Production Story: The Logistics Routing Disaster

A delivery company's routing system calculated optimal routes for 500 daily deliveries. After adding "discount roads" with negative costs (toll rebates), the system started producing impossible routes.

JAVA(33 lines)
Code
Loading syntax highlighter...

The problem: Dijkstra assumes once a vertex is processed, its distance is final. Negative edges violate this assumption - a "longer" path through negative edges might be shorter!

TEXT(12 lines)
Code
Loading syntax highlighter...

The fix:

JAVA(53 lines)
Code
Loading syntax highlighter...

The lesson: Algorithm selection isn't just about performance - it's about correctness. Using Dijkstra on negative-weight graphs gives wrong answers silently.

🧠 Mental Model: Shortest Path Algorithm Selection

TEXT(23 lines)
Code
Loading syntax highlighter...

🔬 Deep Dive: Dijkstra's Algorithm

🎮 Try It Yourself

Watch Dijkstra's algorithm find shortest paths step by step. Observe how the algorithm greedily selects the minimum distance vertex and relaxes edges:

Dijkstra's Algorithm
Time: O((V+E) log V)Space: O(V)
1 / 25
Initialize: dist[0] = 0, all others = ∞. Add source to priority queue.
Real-world uses:GPS navigation, network routing, game pathfinding
⚠️ Limitation:No negative edge weights! Use Bellman-Ford instead
Distance Array (shortest paths from node 0)
Node 0(src)
0
Node 1
∞
Node 2
∞
Node 3
∞
Node 4
∞
Node 5
∞
Relaxation Formula
if dist[u] + weight(u,v) < dist[v] → update dist[v]
Priority Queue (min-heap)(node:distance)
0:0← MIN
Pseudocode
1dijkstra(graph, start):
2  dist[start]=0, dist[*]=∞
3  pq.add((0, start))
4  while pq not empty:
5    (d,u) = pq.extractMin()
6    if visited[u]: continue
7    visited[u] = true
8    for neighbor v of u:
9      if dist[u]+w < dist[v]:
10        dist[v] = dist[u]+w
11        pq.add((dist[v], v))
Variables
start
=0
dist[start]
=0
Keyboard Shortcuts
P Play / Pause
[ Step back
] Step forward
R Reset
Speed
Unvisited
Unvisited
Current
Current
Visited
Visited
P · [ ] · R
Loading visualizer...

The Greedy Insight

Dijkstra works by greedily selecting the unvisited vertex with minimum distance. With non-negative weights, this greedy choice is always correct.

TEXT(14 lines)
Code
Loading syntax highlighter...

Implementation with Priority Queue

JAVA(98 lines)
Code
Loading syntax highlighter...

Dijkstra with Indexed Priority Queue (Optimized)

JAVA(106 lines)
Code
Loading syntax highlighter...

🔬 Deep Dive: Bellman-Ford Algorithm

Handling Negative Weights

JAVA(110 lines)
Code
Loading syntax highlighter...

Why Bellman-Ford Works

TEXT(16 lines)
Code
Loading syntax highlighter...

🔬 Deep Dive: Floyd-Warshall Algorithm

All-Pairs Shortest Paths

JAVA(112 lines)
Code
Loading syntax highlighter...

Floyd-Warshall DP Insight

TEXT(21 lines)
Code
Loading syntax highlighter...

🔬 Deep Dive: A* Search Algorithm

The Heuristic Advantage

A* uses a heuristic function h(v) to estimate distance from v to goal, prioritizing vertices that seem closer to the goal.

JAVA(75 lines)
Code
Loading syntax highlighter...

Common Heuristics

JAVA(35 lines)
Code
Loading syntax highlighter...

A* vs Dijkstra Visualization

TEXT(17 lines)
Code
Loading syntax highlighter...

🔬 Deep Dive: Bidirectional Search

Meeting in the Middle

JAVA(87 lines)
Code
Loading syntax highlighter...

⚠️ Common Mistakes

Mistake 1: Using Dijkstra with Negative Weights

JAVA(10 lines)
Code
Loading syntax highlighter...

Mistake 2: Integer Overflow in Distance Calculation

JAVA(15 lines)
Code
Loading syntax highlighter...

Mistake 3: Not Handling Disconnected Vertices

JAVA(10 lines)
Code
Loading syntax highlighter...

Mistake 4: Wrong Heuristic in A*

JAVA(10 lines)
Code
Loading syntax highlighter...

🐛 Debug This: The Broken Shortest Path

These implementations have bugs. Find and fix them:

JAVA(65 lines)
Code
Loading syntax highlighter...

💡 Hint

Look for:

Initialization of distances
Loop count in Bellman-Ford
Missing negative cycle check
A* should sort by f-score (g + h), not just g-score

✅ Solution

JAVA(84 lines)
Code
Loading syntax highlighter...

Bugs explained:

Dijkstra initialization: dist[i] = graph[src][i] only works if all vertices have direct edges from source. Should initialize to MAX_VALUE and start with source at 0.
Bellman-Ford iterations: Should be V-1 iterations for relaxation, then one more iteration to detect negative cycles. Original had V iterations and no cycle check.
A sorting*: A* must sort by f-score (g + h), not just g-score. Sorting by g-score alone makes it equivalent to Dijkstra, losing the heuristic benefit.

💻 Exercises

Exercise 1: Network Delay Time (LeetCode 743) ⭐⭐

Find time for signal to reach all nodes from source.

JAVA(11 lines)
Code
Loading syntax highlighter...

Exercise 2: Cheapest Flights Within K Stops (LeetCode 787) ⭐⭐⭐

Find cheapest flight with at most K stops.

JAVA(12 lines)
Code
Loading syntax highlighter...

💡 Hint

Use Bellman-Ford with exactly k+1 iterations (k stops = k+1 edges). Or use BFS with level tracking.

Exercise 3: Path with Maximum Probability (LeetCode 1514) ⭐⭐⭐

Find path with highest probability of success.

JAVA(11 lines)
Code
Loading syntax highlighter...

Exercise 4: Shortest Path in Grid with Obstacles (LeetCode 1293) ⭐⭐⭐⭐

Find shortest path in grid where you can eliminate up to k obstacles.

JAVA(10 lines)
Code
Loading syntax highlighter...

Exercise 5: Find Negative Cycle ⭐⭐⭐⭐

Return the actual vertices forming a negative cycle.

JAVA(9 lines)
Code
Loading syntax highlighter...

🎤 Interview Questions

Question 1: When would you use each shortest path algorithm?

Answer:

Algorithm	Use When
BFS	Unweighted graph, need shortest by edge count
Dijkstra	Weighted, non-negative, single source
A*	Single source-target with good heuristic
Bellman-Ford	Has negative weights, need cycle detection
Floyd-Warshall	Need all-pairs, dense graph, V is small

Decision factors:

Negative weights? → Bellman-Ford or Floyd-Warshall
Single source or all pairs?
Graph density (E vs V²)?
Have good heuristic? → Consider A*

Question 2: Why doesn't Dijkstra work with negative weights?

Answer:

Dijkstra's greedy approach assumes: "Once a vertex is processed, its distance is final."

With negative weights, this assumption breaks:

TEXT(17 lines)
Code
Loading syntax highlighter...

Question 3: Explain the A* heuristic requirements

Answer:

A* requires an admissible heuristic: h(v) ≤ actual distance from v to goal.

Why admissibility matters:

If h overestimates, A* might skip the optimal path
Admissible h guarantees optimal solution

Consistency/Monotonicity (stronger): h(u) ≤ cost(u,v) + h(v)

Guarantees A* won't revisit nodes
All consistent heuristics are admissible

Common heuristics:

Manhattan: |dx| + |dy| - admissible for 4-direction grid
Euclidean: √(dx² + dy²) - admissible for any movement
Zero: h(v) = 0 - always admissible, but A* becomes Dijkstra

Trade-off: Higher h (closer to actual) → fewer nodes explored, but more computation per node.

Question 4: How would you detect a negative cycle?

Answer:

Method 1: Bellman-Ford extra iteration

JAVA(6 lines)
Code
Loading syntax highlighter...

Method 2: Floyd-Warshall diagonal check

JAVA(6 lines)
Code
Loading syntax highlighter...

Method 3: DFS with path tracking

Track sum of edge weights on current DFS path
If we return to a vertex with lower total weight, negative cycle found

Finding the actual cycle:

Run Bellman-Ford V iterations (not V-1)
Any vertex updated in V-th iteration is reachable from negative cycle
Trace back through predecessors to find cycle

Question 5: Compare single-source algorithms complexity

Answer:

Algorithm	Time	Space	Notes
BFS	O(V+E)	O(V)	Unweighted only
Dijkstra (binary heap)	O((V+E) log V)	O(V)	No negative weights
Dijkstra (Fibonacci heap)	O(E + V log V)	O(V)	Better for dense graphs
Bellman-Ford	O(VE)	O(V)	Handles negative weights
SPFA	O(VE) worst, O(E) avg	O(V)	Optimized Bellman-Ford

Practical guidance:

Sparse graph (E ≈ V): Dijkstra with binary heap
Dense graph (E ≈ V²): Dijkstra or Bellman-Ford similar
Need negative weights: Bellman-Ford
Unweighted: Always use BFS

📋 Quick Reference

Algorithm Comparison

	Dijkstra	Bellman-Ford	Floyd-Warshall	A*
Type	Greedy	DP	DP	Heuristic
Negative edges	No	Yes	Yes	No
Negative cycles	No	Detects	Detects	No
Single source	Yes	Yes	No (all pairs)	Yes
Time	O((V+E)log V)	O(VE)	O(V³)	O(E) to O(V²)

Code Templates

JAVA(49 lines)
Code
Loading syntax highlighter...

📅 Review Schedule

Day	Focus	Time
Day 1	Read article, implement Dijkstra	60 min
Day 3	Implement Bellman-Ford with cycle detection	30 min
Day 7	Implement A* for grid pathfinding	30 min
Day 14	Solve LeetCode shortest path problems	45 min
Day 30	Review and compare algorithm trade-offs	20 min

🔗 What's Next?

Part 13: Minimum Spanning Tree covers:

Union-Find data structure
Kruskal's algorithm
Prim's algorithm
Borůvka's algorithm
MST applications

Key insight preview: MST asks "connect all vertices with minimum total edge weight" - different from shortest path which asks about paths between specific vertices.

This article is part of the Algorithms Compendium series. For the complete learning path, see Part 0: How to Use This Series.

📋 At a Glance

🎯 What You'll Learn

🔥 Production Story: The Logistics Routing Disaster

🧠 Mental Model: Shortest Path Algorithm Selection

🔬 Deep Dive: Dijkstra's Algorithm

🎮 Try It Yourself

Dijkstra's Algorithm

The Greedy Insight

Implementation with Priority Queue

Dijkstra with Indexed Priority Queue (Optimized)

🔬 Deep Dive: Bellman-Ford Algorithm

Handling Negative Weights

Why Bellman-Ford Works

🔬 Deep Dive: Floyd-Warshall Algorithm

All-Pairs Shortest Paths

Floyd-Warshall DP Insight

🔬 Deep Dive: A* Search Algorithm

The Heuristic Advantage

Common Heuristics

A* vs Dijkstra Visualization

🔬 Deep Dive: Bidirectional Search

Meeting in the Middle

⚠️ Common Mistakes

Mistake 1: Using Dijkstra with Negative Weights

Mistake 2: Integer Overflow in Distance Calculation

Mistake 3: Not Handling Disconnected Vertices

Mistake 4: Wrong Heuristic in A*

🐛 Debug This: The Broken Shortest Path

💻 Exercises

Exercise 1: Network Delay Time (LeetCode 743) ⭐⭐

Exercise 2: Cheapest Flights Within K Stops (LeetCode 787) ⭐⭐⭐

Exercise 3: Path with Maximum Probability (LeetCode 1514) ⭐⭐⭐

Exercise 4: Shortest Path in Grid with Obstacles (LeetCode 1293) ⭐⭐⭐⭐

Exercise 5: Find Negative Cycle ⭐⭐⭐⭐

🎤 Interview Questions

Question 1: When would you use each shortest path algorithm?

Question 2: Why doesn't Dijkstra work with negative weights?

Question 3: Explain the A* heuristic requirements

Question 4: How would you detect a negative cycle?

Question 5: Compare single-source algorithms complexity

📋 Quick Reference

Algorithm Comparison

Code Templates

📅 Review Schedule

🔗 What's Next?

Tags:

Dijkstra's Algorithm