Shortest Path (Dijkstra, Bellman-Ford)

Overview

Shortest path algorithms compute the minimum-cost path between vertices in a weighted graph. These algorithms solve fundamental problems in network routing, GPS navigation, logistics optimization, and countless other domains where finding optimal routes through connected systems is required.

Dijkstra's algorithm and the Bellman-Ford algorithm represent two distinct approaches to the single-source shortest path problem, where the goal is to find the shortest paths from a starting vertex to all other vertices in the graph. Dijkstra's algorithm achieves superior performance through a greedy approach that requires non-negative edge weights. The Bellman-Ford algorithm trades performance for versatility, handling graphs with negative edge weights and detecting negative cycles that make shortest paths undefined.

The key distinction between these algorithms lies in their edge weight requirements and performance characteristics. Dijkstra's algorithm operates in O(E + V log V) time with appropriate data structures but fails on graphs containing negative weights. The Bellman-Ford algorithm runs in O(V × E) time but correctly processes negative weights and identifies when negative cycles prevent shortest path computation.

# Graph representation for shortest path problems
graph = {
  'A' => [['B', 4], ['C', 2]],
  'B' => [['C', 1], ['D', 5]],
  'C' => [['D', 8], ['E', 10]],
  'D' => [['E', 2]],
  'E' => []
}

# Dijkstra finds: A->C->B->D->E (cost: 9)
# Path: A(0) -> C(2) -> B(3) -> D(8) -> E(10)

Both algorithms maintain distance estimates that improve iteratively until optimal values are discovered. The algorithms differ in how they select which vertices to process and when they terminate. Understanding these differences allows developers to select the appropriate algorithm based on graph characteristics and performance requirements.

Key Principles

Shortest path algorithms operate on directed or undirected weighted graphs, where edges have associated costs representing distance, time, or other metrics. The single-source shortest path problem requires finding minimum-cost paths from a designated source vertex to all reachable vertices. The shortest path between two vertices may traverse multiple intermediate vertices, with the total cost equal to the sum of edge weights along the path.

Distance estimates form the core data structure in both algorithms. Each vertex maintains a tentative distance from the source, initialized to infinity except for the source vertex itself (distance zero). As the algorithm progresses, these estimates decrease and eventually converge to actual shortest distances. Once a vertex's distance becomes final, no future updates can improve it under correct algorithm operation.

Relaxation is the fundamental operation for improving distance estimates. When examining an edge from vertex u to vertex v with weight w, relaxation checks whether the path through u provides a shorter route to v than previously known. If distance[u] + w < distance[v], the algorithm updates distance[v] and records u as v's predecessor in the shortest path tree. Both Dijkstra and Bellman-Ford rely on relaxation but differ in how they order these operations.

Dijkstra's greedy selection processes vertices in order of their current distance estimates. The algorithm repeatedly selects the unprocessed vertex with minimum distance, marks it as processed, and relaxes all outgoing edges. This greedy choice works correctly when all edge weights are non-negative because processing a vertex with minimum current distance guarantees that distance is optimal. No future path can improve it since adding positive weights can only increase total distance.

Bellman-Ford's exhaustive approach relaxes all edges repeatedly without assuming anything about edge weights. After k iterations, the algorithm has correctly computed shortest paths using at most k edges. Since shortest paths in a graph with V vertices contain at most V-1 edges (assuming no negative cycles), V-1 iterations suffice to find all shortest paths. A final iteration detects negative cycles: if any distance can still improve, a negative cycle exists.

Priority queue optimization for Dijkstra reduces time complexity from O(V²) to O(E + V log V). The naive approach scans all vertices to find the minimum distance vertex, requiring O(V) time per iteration and O(V²) total. Using a binary heap priority queue reduces vertex selection to O(log V) and produces total time O(E log V) since each edge relaxation may trigger a heap update. Fibonacci heaps achieve theoretical O(E + V log V) but have higher constant factors.

Negative weight handling distinguishes the algorithms fundamentally. Dijkstra's greedy selection assumes that processing a vertex finalizes its distance. Negative edges violate this assumption because a later path through a negative edge could reduce a previously finalized distance. Bellman-Ford makes no such assumption and correctly handles negative weights through exhaustive edge relaxation. However, negative cycles (cycles whose total weight is negative) make shortest paths undefined since repeatedly traversing the cycle reduces path cost indefinitely.

Path reconstruction requires storing predecessor information during distance updates. When relaxing an edge from u to v, the algorithm records u as v's predecessor if the relaxation succeeds. After finding shortest distances, the path from source to any vertex v can be reconstructed by following predecessors backward from v to the source, then reversing the sequence.

# Relaxation operation
def relax(u, v, weight, distances, predecessors)
  new_distance = distances[u] + weight
  if new_distance < distances[v]
    distances[v] = new_distance
    predecessors[v] = u
    true  # Relaxation succeeded
  else
    false  # No improvement
  end
end

Ruby Implementation

Ruby implementations of shortest path algorithms require graph representation, priority queue management for Dijkstra, and careful handling of infinite distances. The adjacency list representation stores each vertex's outgoing edges efficiently, while distance tracking uses hashes with default infinity values.

Dijkstra's algorithm in Ruby uses a priority queue to select vertices efficiently. The PQueue gem provides a binary heap implementation, though Ruby's standard library SortedSet can substitute at the cost of reduced performance. The algorithm maintains a set of visited vertices to prevent reprocessing.

require 'pqueue'

def dijkstra(graph, source)
  distances = Hash.new(Float::INFINITY)
  predecessors = {}
  distances[source] = 0
  
  pq = PQueue.new { |a, b| distances[a] < distances[b] }
  pq.push(source)
  visited = Set.new
  
  until pq.empty?
    current = pq.pop
    next if visited.include?(current)
    visited.add(current)
    
    graph[current].each do |neighbor, weight|
      next if visited.include?(neighbor)
      
      new_distance = distances[current] + weight
      if new_distance < distances[neighbor]
        distances[neighbor] = new_distance
        predecessors[neighbor] = current
        pq.push(neighbor)
      end
    end
  end
  
  [distances, predecessors]
end

# Example usage
graph = {
  'A' => [['B', 7], ['C', 3]],
  'B' => [['D', 1], ['C', 2]],
  'C' => [['D', 4], ['E', 6]],
  'D' => [['E', 2]],
  'E' => []
}

distances, predecessors = dijkstra(graph, 'A')
# distances: {'A'=>0, 'C'=>3, 'B'=>5, 'D'=>6, 'E'=>8}

Bellman-Ford algorithm requires no priority queue but iterates over all edges V-1 times. Ruby's straightforward iteration makes the implementation readable. The algorithm collects all edges into a single array for repeated processing.

def bellman_ford(graph, source)
  # Initialize distances
  distances = Hash.new(Float::INFINITY)
  predecessors = {}
  vertices = graph.keys
  
  distances[source] = 0
  
  # Collect all edges
  edges = []
  graph.each do |u, neighbors|
    neighbors.each do |v, weight|
      edges << [u, v, weight]
    end
  end
  
  # Relax edges V-1 times
  (vertices.size - 1).times do
    edges.each do |u, v, weight|
      if distances[u] != Float::INFINITY && 
         distances[u] + weight < distances[v]
        distances[v] = distances[u] + weight
        predecessors[v] = u
      end
    end
  end
  
  # Check for negative cycles
  edges.each do |u, v, weight|
    if distances[u] != Float::INFINITY && 
       distances[u] + weight < distances[v]
      raise "Graph contains negative cycle"
    end
  end
  
  [distances, predecessors]
end

# Handling negative weights
graph_with_negatives = {
  'A' => [['B', 4], ['C', 2]],
  'B' => [['C', -3], ['D', 2]],
  'C' => [['D', 3]],
  'D' => []
}

distances, predecessors = bellman_ford(graph_with_negatives, 'A')
# distances: {'A'=>0, 'C'=>1, 'B'=>4, 'D'=>4}
# Path A->B->C is cheaper than A->C due to negative edge

Path reconstruction follows predecessors backward from the target vertex. Ruby's recursive approach provides clean path building, though iterative methods avoid stack overflow on very long paths.

def reconstruct_path(predecessors, source, target)
  return nil unless predecessors.key?(target)
  
  path = []
  current = target
  
  while current != source
    path.unshift(current)
    current = predecessors[current]
    return nil if current.nil?
  end
  
  path.unshift(source)
  path
end

# Find path from A to E
path = reconstruct_path(predecessors, 'A', 'E')
# => ['A', 'C', 'D', 'E']

Bidirectional search optimization runs Dijkstra simultaneously from source and target, terminating when the searches meet. This approach reduces the search space for single-target queries but requires careful termination detection.

def bidirectional_dijkstra(graph, reverse_graph, source, target)
  forward_distances = Hash.new(Float::INFINITY)
  backward_distances = Hash.new(Float::INFINITY)
  forward_distances[source] = 0
  backward_distances[target] = 0
  
  forward_pq = PQueue.new { |a, b| forward_distances[a] < forward_distances[b] }
  backward_pq = PQueue.new { |a, b| backward_distances[a] < backward_distances[b] }
  forward_pq.push(source)
  backward_pq.push(target)
  
  forward_visited = Set.new
  backward_visited = Set.new
  best_distance = Float::INFINITY
  meeting_point = nil
  
  until forward_pq.empty? && backward_pq.empty?
    # Forward step
    unless forward_pq.empty?
      current = forward_pq.pop
      unless forward_visited.include?(current)
        forward_visited.add(current)
        
        # Check if searches met
        if backward_visited.include?(current)
          total = forward_distances[current] + backward_distances[current]
          if total < best_distance
            best_distance = total
            meeting_point = current
          end
        end
        
        graph[current].each do |neighbor, weight|
          new_dist = forward_distances[current] + weight
          if new_dist < forward_distances[neighbor]
            forward_distances[neighbor] = new_dist
            forward_pq.push(neighbor)
          end
        end
      end
    end
    
    # Backward step (similar logic with reverse_graph)
    # ... backward expansion code
  end
  
  best_distance
end

All-pairs shortest paths extends single-source algorithms to compute distances between all vertex pairs. Running Dijkstra from each vertex achieves O(V × E + V² log V) time, acceptable for sparse graphs. Dense graphs benefit from the Floyd-Warshall algorithm's O(V³) time with simpler implementation.

def all_pairs_dijkstra(graph)
  all_distances = {}
  
  graph.keys.each do |source|
    distances, _ = dijkstra(graph, source)
    all_distances[source] = distances
  end
  
  all_distances
end

# Access distance from any vertex to any other
all_distances = all_pairs_dijkstra(graph)
distance_b_to_e = all_distances['B']['E']

Performance Considerations

Time complexity analysis reveals fundamental differences between Dijkstra and Bellman-Ford algorithms. Dijkstra with a binary heap priority queue runs in O((V + E) log V) time because each vertex enters and exits the queue once (O(V log V)) and each edge may trigger a priority update (O(E log V)). The Fibonacci heap reduces this to O(E + V log V) theoretical time but has larger constant factors and implementation complexity that rarely justifies its use in practice.

Bellman-Ford's O(V × E) time complexity comes from relaxing all E edges during each of V-1 iterations. For dense graphs where E approaches V², this becomes O(V³), significantly slower than Dijkstra's O(V² log V). Sparse graphs with E proportional to V see O(V²) Bellman-Ford performance, still slower than Dijkstra but often acceptable when negative weights are present.

Space complexity for both algorithms requires O(V) for distance and predecessor storage plus O(E) for the graph representation. Dijkstra adds O(V) for the priority queue, while Bellman-Ford uses O(E) temporarily to collect edges for repeated processing. Both algorithms have linear space requirements relative to input size.

Early termination in Dijkstra occurs naturally when the target vertex is processed, since no better path to that vertex can exist afterward. Single-target queries benefit significantly from this property, examining only a subset of the graph when the target is reachable via short paths. Bellman-Ford cannot terminate early in the general case but can detect convergence when an iteration produces no distance updates, indicating optimal distances are found.

def dijkstra_early_termination(graph, source, target)
  distances = Hash.new(Float::INFINITY)
  distances[source] = 0
  
  pq = PQueue.new { |a, b| distances[a] < distances[b] }
  pq.push(source)
  visited = Set.new
  
  until pq.empty?
    current = pq.pop
    
    # Early termination when target reached
    return distances[target] if current == target
    
    next if visited.include?(current)
    visited.add(current)
    
    graph[current].each do |neighbor, weight|
      next if visited.include?(neighbor)
      new_distance = distances[current] + weight
      if new_distance < distances[neighbor]
        distances[neighbor] = new_distance
        pq.push(neighbor)
      end
    end
  end
  
  Float::INFINITY
end

Graph density significantly impacts algorithm selection. Sparse graphs with E much smaller than V² favor Dijkstra's O(E log V) performance. Dense graphs approach E = V², making Dijkstra's time O(V² log V). For very dense graphs, a simple O(V²) implementation scanning for minimum distances without a priority queue may outperform heap-based versions due to better cache locality and lower constant factors.

Priority queue implementation creates substantial performance variation in Dijkstra's algorithm. Ruby's PQueue gem provides binary heaps with O(log V) operations. Array-based scanning achieves O(V) selection but O(V²) total time. For small graphs (V < 100), the simpler array approach often runs faster due to lower overhead. Large graphs require heap-based selection for acceptable performance.

Negative cycle detection in Bellman-Ford adds one final iteration over all edges after V-1 relaxation rounds. This detection is free in terms of asymptotic complexity but adds 1/(V-1) overhead to practical runtime. Applications that know negative cycles cannot exist can skip this check, though the safety guarantee usually justifies the cost.

Parallel processing opportunities differ between algorithms. Dijkstra's sequential vertex processing resists parallelization because each step depends on finding the global minimum distance vertex. Bellman-Ford's edge relaxation within each iteration can be parallelized since relaxations are independent, though updates to shared distance arrays require synchronization. GPU implementations of Bellman-Ford can achieve significant speedups on large graphs.

Cache efficiency affects practical performance beyond asymptotic analysis. Dijkstra's priority queue exhibits poor cache locality when heap operations access scattered memory locations. Bellman-Ford's sequential edge processing has better cache behavior, particularly when edges are stored contiguously. For graphs that fit in cache, these microarchitectural effects can dominate algorithmic complexity.

# Performance comparison on random graphs
require 'benchmark'

def generate_random_graph(vertices, edges, max_weight)
  graph = Hash.new { |h, k| h[k] = [] }
  vertex_list = (0...vertices).to_a
  
  edges.times do
    u = vertex_list.sample
    v = vertex_list.sample
    next if u == v
    weight = rand(1..max_weight)
    graph[u] << [v, weight]
  end
  
  graph
end

graph = generate_random_graph(1000, 5000, 100)

Benchmark.bm do |x|
  x.report("Dijkstra:") { dijkstra(graph, 0) }
  x.report("Bellman-Ford:") { bellman_ford(graph, 0) }
end

# Typical results on sparse graph (E = 5V):
# Dijkstra:      0.15 seconds
# Bellman-Ford:  2.3 seconds

Practical Examples

Road network navigation represents the classic shortest path application. Graph vertices represent intersections, edges represent road segments, and weights represent travel time or distance. Dijkstra's algorithm finds optimal routes when all travel times are positive, which holds for typical road networks.

# City road network
roads = {
  'Home' => [['School', 10], ['Park', 15]],
  'School' => [['Library', 5], ['Store', 8]],
  'Park' => [['Library', 12], ['Store', 7]],
  'Library' => [['Hospital', 6]],
  'Store' => [['Hospital', 9]],
  'Hospital' => []
}

distances, predecessors = dijkstra(roads, 'Home')

# Find shortest route to Hospital
hospital_distance = distances['Hospital']  # => 21
route = reconstruct_path(predecessors, 'Home', 'Hospital')
# => ['Home', 'School', 'Library', 'Hospital']

# Route segments
route.each_cons(2) do |from, to|
  segment_cost = roads[from].find { |dest, _| dest == to }[1]
  puts "#{from} -> #{to}: #{segment_cost} minutes"
end
# Home -> School: 10 minutes
# School -> Library: 5 minutes
# Library -> Hospital: 6 minutes

Network packet routing uses shortest path algorithms to determine optimal packet forwarding paths. Link weights represent latency, bandwidth, or cost. Routers run distributed versions of Dijkstra's algorithm in protocols like OSPF (Open Shortest Path First) to compute routing tables.

# Network topology with latency weights (milliseconds)
network = {
  'Router_A' => [['Router_B', 5], ['Router_C', 2]],
  'Router_B' => [['Router_D', 3], ['Router_E', 7]],
  'Router_C' => [['Router_B', 1], ['Router_D', 10]],
  'Router_D' => [['Router_E', 2]],
  'Router_E' => []
}

distances, predecessors = dijkstra(network, 'Router_A')

# Routing table for Router_A
network.keys.each do |destination|
  next if destination == 'Router_A'
  
  path = reconstruct_path(predecessors, 'Router_A', destination)
  next_hop = path[1] if path && path.size > 1
  latency = distances[destination]
  
  puts "To #{destination}: next_hop=#{next_hop}, latency=#{latency}ms"
end
# To Router_E: next_hop=Router_C, latency=7ms
# (path: Router_A -> Router_C -> Router_B -> Router_D -> Router_E)

Currency arbitrage detection uses Bellman-Ford to find negative cycles in exchange rate graphs. Converting edge weights to logarithms transforms the product of exchange rates into a sum, where negative cycles indicate arbitrage opportunities (profit from currency conversions).

# Exchange rates (simplified)
exchanges = {
  'USD' => [['EUR', 0.85], ['GBP', 0.73]],
  'EUR' => [['GBP', 0.86], ['JPY', 130.0]],
  'GBP' => [['USD', 1.38], ['JPY', 150.0]],
  'JPY' => [['USD', 0.0067], ['EUR', 0.0077]]
}

# Convert to negative log weights to detect arbitrage
require 'math'

log_graph = {}
exchanges.each do |from, conversions|
  log_graph[from] = conversions.map do |to, rate|
    [to, -Math.log(rate)]
  end
end

begin
  distances, _ = bellman_ford(log_graph, 'USD')
  puts "No arbitrage opportunity found"
rescue => e
  puts "Arbitrage detected: #{e.message}"
  # Negative cycle exists - profit possible through currency loop
end

Dependency resolution in package managers uses shortest path algorithms to find minimal dependency chains. Vertices represent package versions, edges represent dependencies, and weights represent version distances or compatibility costs.

# Package dependency graph
dependencies = {
  'app-v1.0' => [['lib-v2.0', 1], ['util-v1.5', 1]],
  'lib-v2.0' => [['core-v3.0', 1], ['helper-v1.0', 2]],
  'lib-v1.9' => [['core-v2.5', 1], ['helper-v1.0', 1]],
  'util-v1.5' => [['core-v3.0', 1]],
  'core-v3.0' => [],
  'core-v2.5' => [],
  'helper-v1.0' => []
}

# Find minimal dependency chain to core
distances, predecessors = dijkstra(dependencies, 'app-v1.0')

core_packages = dependencies.keys.select { |k| k.start_with?('core') }
best_core = core_packages.min_by { |pkg| distances[pkg] }

dependency_chain = reconstruct_path(predecessors, 'app-v1.0', best_core)
puts "Minimal dependency chain: #{dependency_chain.join(' -> ')}"
# => app-v1.0 -> lib-v2.0 -> core-v3.0

Project scheduling with precedence constraints models tasks as vertices and dependencies as edges. Weights represent task durations. The longest path (negated shortest path) through the dependency graph determines the critical path and minimum project completion time.

# Project tasks with dependencies and durations
tasks = {
  'Start' => [['Design', 0], ['Research', 0]],
  'Research' => [['Design', 3]],
  'Design' => [['Prototype', 5], ['Documentation', 5]],
  'Prototype' => [['Testing', 7]],
  'Documentation' => [['Testing', 2]],
  'Testing' => [['Deploy', 4]],
  'Deploy' => []
}

# Negate weights for longest path
negated_tasks = {}
tasks.each do |task, deps|
  negated_tasks[task] = deps.map { |dep, dur| [dep, -dur] }
end

distances, predecessors = bellman_ford(negated_tasks, 'Start')

# Critical path and project duration
critical_duration = -distances['Deploy']
critical_path = reconstruct_path(predecessors, 'Start', 'Deploy')

puts "Project duration: #{critical_duration} days"
puts "Critical path: #{critical_path.join(' -> ')}"
# => Project duration: 16 days
# => Critical path: Start -> Design -> Prototype -> Testing -> Deploy

Design Considerations

Algorithm selection between Dijkstra and Bellman-Ford depends primarily on edge weight characteristics. Dijkstra's superior performance makes it the default choice for graphs with non-negative weights. The Bellman-Ford algorithm is necessary only when negative weights are present or when negative cycle detection is required.

Non-negative weight guarantee enables Dijkstra's greedy optimization. Real-world scenarios often naturally satisfy this constraint: physical distances, time durations, and costs are inherently non-negative. Converting problems to ensure non-negative weights through transformations like Johnson's algorithm allows using Dijkstra when the original formulation contains negative weights.

Negative weight scenarios arise in specific domains. Financial graphs modeling profit and loss contain negative edges representing costs or penalties. Difference constraints in constraint satisfaction problems naturally encode negative weights. The Bellman-Ford algorithm handles these cases correctly where Dijkstra would produce incorrect results.

Sparse vs dense graphs influence implementation strategy. Sparse graphs with E = O(V) favor Dijkstra with priority queues achieving near-linear performance. Dense graphs approaching E = O(V²) may benefit from simpler array-based minimum distance selection avoiding priority queue overhead. The crossover point typically occurs around E = V log V, though constant factors vary by implementation.

Single-target vs all-targets queries determine whether early termination matters. Applications needing one shortest path benefit from Dijkstra's ability to stop when the target is reached. Routing protocols and distance matrix computation require all shortest paths, making early termination impossible and favoring implementations optimized for processing all vertices.

Bidirectional search trade-offs reduce search space for single-target queries at the cost of implementation complexity. The technique works best when graphs have high diameter (long shortest paths between distant vertices) and poor branching factor, allowing the two searches to meet quickly. Dense graphs with short paths gain little from bidirectional search.

Dynamic graph updates present challenges for pre-computed shortest paths. Adding edges may create better paths requiring updates, while removing edges may invalidate existing paths. Incremental algorithms like D* Lite maintain shortest path trees under graph modifications more efficiently than recomputing from scratch, but add significant implementation complexity.

# Choosing between algorithms based on graph properties
def select_shortest_path_algorithm(graph)
  has_negative = graph.any? do |_, edges|
    edges.any? { |_, weight| weight < 0 }
  end
  
  if has_negative
    puts "Graph has negative weights - using Bellman-Ford"
    :bellman_ford
  else
    vertex_count = graph.keys.size
    edge_count = graph.values.map(&:size).sum
    
    if edge_count < vertex_count * Math.log(vertex_count)
      puts "Sparse graph - using Dijkstra with priority queue"
      :dijkstra_pq
    else
      puts "Dense graph - using Dijkstra with array scan"
      :dijkstra_array
    end
  end
end

Preprocessing trade-offs offer performance improvements for repeated queries. Computing all-pairs shortest paths once with Floyd-Warshall (O(V³)) enables O(1) distance lookups afterward. This approach suits applications with static graphs and frequent distance queries. Dynamic graphs or large vertex counts make preprocessing impractical.

Approximate algorithms sacrifice optimality for performance on very large graphs. A* search uses heuristics to guide exploration toward targets, reducing the search space. Contraction hierarchies pre-process road networks to enable millisecond queries on continental-scale graphs. These techniques solve different problems than exact shortest paths but often provide acceptable solutions when exact algorithms are too slow.

Distributed computation becomes necessary for graphs exceeding single-machine memory. Distributed Bellman-Ford naturally parallelizes edge relaxation across machines, though communication overhead dominates for small graphs. Graph partitioning strategies minimize cross-partition edges to reduce synchronization. Distributed Dijkstra faces challenges from the sequential nature of greedy vertex selection.

Common Pitfalls

Negative weight edges in Dijkstra produce incorrect results without warning. The algorithm completes successfully but reports suboptimal distances because the greedy assumption fails. Testing edge weights before selecting Dijkstra prevents this silent failure mode.

# Dijkstra fails on negative weights
graph_negative = {
  'A' => [['B', 4], ['C', 2]],
  'B' => [['C', -5]],  # Negative edge
  'C' => []
}

distances, _ = dijkstra(graph_negative, 'A')
# distances['C'] = 2 (wrong! actual shortest is A->B->C = -1)

# Validation before running
def validate_for_dijkstra(graph)
  graph.each do |vertex, edges|
    edges.each do |neighbor, weight|
      raise "Negative edge #{vertex}->#{neighbor}" if weight < 0
    end
  end
end

Infinite distance comparisons require careful handling. Ruby's Float::INFINITY supports arithmetic correctly, but some operations produce unexpected results. Checking for infinity before arithmetic operations avoids issues.

# Infinity arithmetic
distance = Float::INFINITY
new_distance = distance + 5  # => Infinity (correct)

# Comparison pitfall
if distance < Float::INFINITY  # => false
  # This branch never executes
end

# Correct check
if distance != Float::INFINITY
  # Process reachable vertex
end

Priority queue duplicate entries in Dijkstra implementations can add vertices to the queue multiple times with different priorities. Processing logic must skip already-visited vertices to avoid redundant work and incorrect results.

# Bug: processing vertices multiple times
def dijkstra_buggy(graph, source)
  distances = Hash.new(Float::INFINITY)
  distances[source] = 0
  pq = PQueue.new { |a, b| distances[a] < distances[b] }
  pq.push(source)
  
  until pq.empty?
    current = pq.pop
    # Missing: check if already visited
    
    graph[current].each do |neighbor, weight|
      new_distance = distances[current] + weight
      if new_distance < distances[neighbor]
        distances[neighbor] = new_distance
        pq.push(neighbor)  # May create duplicates
      end
    end
  end
  
  distances
end

# Fix: track visited vertices
visited = Set.new
until pq.empty?
  current = pq.pop
  next if visited.include?(current)  # Skip duplicates
  visited.add(current)
  # ... rest of processing
end

Disconnected graph handling requires checking whether vertices are reachable. Distances remain infinite for unreachable vertices, which can cause errors if code assumes all vertices are reachable. Path reconstruction must verify that predecessors exist.

# Disconnected graph
graph_disconnected = {
  'A' => [['B', 1]],
  'B' => [],
  'C' => [['D', 1]],
  'D' => []
}

distances, predecessors = dijkstra(graph_disconnected, 'A')
# distances['C'] = Infinity (unreachable)

# Safe path reconstruction
def safe_reconstruct_path(predecessors, source, target)
  return [source] if source == target
  return nil unless predecessors.key?(target)  # Unreachable
  
  path = [target]
  current = target
  
  while current != source
    current = predecessors[current]
    return nil if current.nil?  # Broken path
    path.unshift(current)
  end
  
  path
end

Bellman-Ford iteration count errors occur when using fewer than V-1 iterations. The algorithm requires V-1 iterations to guarantee correctness for all graph shapes. Using fewer iterations works for some graphs but fails on others with longer shortest paths.

# Bug: insufficient iterations
def bellman_ford_buggy(graph, source)
  distances = Hash.new(Float::INFINITY)
  distances[source] = 0
  
  # Wrong: using V/2 iterations
  (graph.keys.size / 2).times do
    # ... relaxation code
  end
  
  distances
end

# Fix: always use V-1 iterations
(graph.keys.size - 1).times do
  # ... relaxation code
end

Missing negative cycle detection allows Bellman-Ford to return incorrect results when negative cycles exist. The final iteration to check for further improvements is essential for correctness guarantees.

Hash initialization errors with distance storage can cause bugs when vertices are not pre-registered in the hash. Using Hash.new with a default value of infinity ensures unvisited vertices have correct initial distances.

# Bug: missing vertices in hash
distances = {}  # No default value
distances[source] = 0

# Later: distances[unknown_vertex] returns nil, not infinity
if distances[vertex] + weight < distances[neighbor]  # nil + weight => error
  # ...
end

# Fix: use default value
distances = Hash.new(Float::INFINITY)
distances[source] = 0

Predecessor tracking omission prevents path reconstruction. Storing only distances suffices for queries about path costs but fails when actual paths are needed. Adding predecessor tracking has negligible overhead and provides essential functionality.

Edge weight integer overflow in languages with fixed-size integers can cause wraparound errors when computing path distances. Ruby's automatic bignum conversion prevents this issue, but implementations in other languages require careful consideration of maximum path weights.

Reference

Algorithm Complexity Comparison

Key Operations

Ruby Implementation Template

# Dijkstra's algorithm with priority queue
def dijkstra(graph, source)
  distances = Hash.new(Float::INFINITY)
  predecessors = {}
  distances[source] = 0
  
  pq = PQueue.new { |a, b| distances[a] < distances[b] }
  pq.push(source)
  visited = Set.new
  
  until pq.empty?
    current = pq.pop
    next if visited.include?(current)
    visited.add(current)
    
    graph[current].each do |neighbor, weight|
      next if visited.include?(neighbor)
      
      new_distance = distances[current] + weight
      if new_distance < distances[neighbor]
        distances[neighbor] = new_distance
        predecessors[neighbor] = current
        pq.push(neighbor)
      end
    end
  end
  
  [distances, predecessors]
end

# Bellman-Ford algorithm with negative cycle detection
def bellman_ford(graph, source)
  distances = Hash.new(Float::INFINITY)
  predecessors = {}
  vertices = graph.keys
  distances[source] = 0
  
  edges = []
  graph.each do |u, neighbors|
    neighbors.each { |v, w| edges << [u, v, w] }
  end
  
  (vertices.size - 1).times do
    edges.each do |u, v, weight|
      if distances[u] != Float::INFINITY && 
         distances[u] + weight < distances[v]
        distances[v] = distances[u] + weight
        predecessors[v] = u
      end
    end
  end
  
  edges.each do |u, v, weight|
    if distances[u] != Float::INFINITY && 
       distances[u] + weight < distances[v]
      raise "Graph contains negative cycle"
    end
  end
  
  [distances, predecessors]
end

# Path reconstruction
def reconstruct_path(predecessors, source, target)
  return [source] if source == target
  return nil unless predecessors.key?(target)
  
  path = []
  current = target
  
  while current != source
    path.unshift(current)
    current = predecessors[current]
    return nil if current.nil?
  end
  
  path.unshift(source)
  path
end

Graph Representation Formats

Algorithm Selection Decision Matrix

Common Pitfalls Checklist