Shortest Path Algorithms
Shortest path algorithms find the minimum-cost path between vertices in a weighted graph. Dijkstra's handles non-negative weights in O((V+E) log V), Bellman-Ford handles negative weights in O(VE), and Floyd-Warshall finds all-pairs shortest paths in O(V^3).
Shortest Path Problem Overview
The shortest path problem asks: given a weighted graph and a source vertex, what is the minimum-cost path to every other vertex?
Choosing the right algorithm depends on the graph properties:
- Dijkstra's Algorithm — Non-negative edge weights only. O((V+E) log V) with a min-heap. The standard choice for most applications. - Bellman-Ford — Handles negative edge weights. Detects negative cycles. O(VE). Used in routing protocols (RIP, BGP). - Floyd-Warshall — All-pairs shortest paths. O(V^3). Best when you need distances between all pairs of vertices. - **A* Search** — Dijkstra with a heuristic. Faster in practice for single-target shortest path (GPS navigation).
Dijkstra's Algorithm
Dijkstra's algorithm uses a greedy approach with a min-heap (priority queue). It always processes the unvisited vertex with the smallest known distance first.
Algorithm: 1. Initialize distances: source = 0, all others = infinity 2. Add source to min-heap 3. While heap is not empty: a. Pop vertex u with minimum distance b. For each neighbor v of u: if dist[u] + weight(u,v) < dist[v], update dist[v] and push to heap
import heapq
from collections import defaultdict
def dijkstra(graph, source, n):
"""
graph: adjacency list {u: [(v, weight), ...]}
source: starting vertex
n: number of vertices
Returns: dist[] array with shortest distances from source
"""
dist = [float('inf')] * n
dist[source] = 0
prev = [-1] * n # For path reconstruction
heap = [(0, source)] # (distance, vertex)
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue # Outdated entry in heap, skip
for v, weight in graph[u]:
new_dist = dist[u] + weight
if new_dist < dist[v]:
dist[v] = new_dist
prev[v] = u
heapq.heappush(heap, (new_dist, v))
return dist, prev
def reconstruct_path(prev, source, target):
path = []
current = target
while current != -1:
path.append(current)
current = prev[current]
path.reverse()
return path if path[0] == source else []
# Test graph (0-indexed vertices)
graph = defaultdict(list)
edges = [(0,1,4),(0,2,1),(2,1,2),(1,3,1),(2,3,5)]
for u, v, w in edges:
graph[u].append((v, w))
graph[v].append((u, w))
dist, prev = dijkstra(graph, 0, 4)
print("Distances from 0:", dist) # [0, 3, 1, 4]
print("Path 0->3:", reconstruct_path(prev, 0, 3)) # [0, 2, 1, 3]Bellman-Ford Algorithm
Bellman-Ford handles negative edge weights by relaxing all edges V-1 times. It also detects negative cycles (a cycle whose total weight is negative — shortest path is undefined).
def bellman_ford(n, edges, source):
"""
n: number of vertices
edges: list of (u, v, weight)
Returns: (dist[], has_negative_cycle)
"""
dist = [float('inf')] * n
dist[source] = 0
# Relax all edges V-1 times
for _ in range(n - 1):
updated = False
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
updated = True
if not updated:
break # Early termination if no updates
# Check for negative cycles (V-th relaxation)
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return dist, True # Negative cycle detected!
return dist, False
# Test with negative edges
edges = [(0,1,4),(0,2,5),(1,3,-3),(2,1,-4),(3,2,2)]
dist, neg_cycle = bellman_ford(4, edges, 0)
print("Distances:", dist)
print("Negative cycle:", neg_cycle)Floyd-Warshall: All-Pairs Shortest Paths
Floyd-Warshall computes shortest paths between all pairs of vertices using dynamic programming. For each intermediate vertex k, it checks if going through k improves the path from i to j.
def floyd_warshall(n, edges):
"""
Returns dist[i][j] = shortest path from i to j
"""
INF = float('inf')
dist = [[INF] * n for _ in range(n)]
# Distance from a vertex to itself is 0
for i in range(n):
dist[i][i] = 0
# Initialize with direct edges
for u, v, w in edges:
dist[u][v] = min(dist[u][v], w)
dist[v][u] = min(dist[v][u], w) # Undirected
# Core DP: try each vertex k as intermediate
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
# Check for negative cycles (diagonal becomes negative)
for i in range(n):
if dist[i][i] < 0:
print("Negative cycle detected!")
return None
return dist
# Test
edges = [(0,1,3),(0,3,7),(1,0,8),(1,2,2),(2,0,5),(2,3,1),(3,0,2)]
dist = floyd_warshall(4, edges)
if dist:
print("All-pairs distances:")
for row in dist:
print([x if x != float('inf') else 'INF' for x in row])Algorithm Comparison and Selection Guide
Choosing the right shortest path algorithm:
- Dijkstra's — Use when: all edge weights are non-negative, single source. O((V+E) log V). Best for GPS, network routing.
- Bellman-Ford — Use when: negative edge weights exist, need negative cycle detection. O(VE). Used in BGP routing protocol.
- Floyd-Warshall — Use when: need all-pairs shortest paths, graph is dense, V is small (< 500). O(V^3).
- A* — Use when: single source to single target, good heuristic available. Faster than Dijkstra's in practice for maps.
- For unweighted graphs, use BFS — it finds shortest paths in O(V+E) without a priority queue.
Key Takeaways
- Dijkstra's uses a min-heap to greedily process vertices in order of distance — O((V+E) log V), non-negative weights only.
- Bellman-Ford relaxes all edges V-1 times — O(VE), handles negative weights, detects negative cycles.
- Floyd-Warshall uses DP to find all-pairs shortest paths in O(V^3) — best for small dense graphs.
- For unweighted graphs, BFS finds shortest paths in O(V+E) without any priority queue overhead.
- Negative cycles make shortest paths undefined — always check for them when negative weights are present.
Contact Us
Have a question or feedback? Fill out the form below or reach us directly at support@nvaitraining.com