Shortest Path in Unweighted Graph

  # ----------------------------------------
  # 2. Shortest Distance using BFS
  #
  # Input:
  #   edges: array of [u, v] pairs
  #   start: starting node (integer or string)
  # Output:
  #   Hash of distances from start to each reachable node
  #
  # Time Complexity: O(N + E)
  # Space Complexity: O(N)
  # Example: bfs_shortest_paths([[0, 1], [1, 2], [2, 3]], 0)
  # Output: {0 => 0, 1 => 1, 2 => 2, 3 => 3}
  # Example: bfs_shortest_paths([['A', 'B'], ['B', 'C'], ['C', 'D']], 'A')
  # Output: {A => 0, B => 1, C => 2, D => 3}
  # ----------------------------------------
  def bfs_shortest_paths(edges, start)
    graph = Hash.new { |h, k| h[k] = [] }
    edges.each { |u, v| graph[u] << v; graph[v] << u }

    distances = Hash.new(-1)
    distances[start] = 0
    queue = [start]

    until queue.empty?
      current = queue.shift
      puts "Visiting #{current}, distance: #{distances[current]}"
      graph[current].each do |neighbor|
        next if distances[neighbor] != -1
        distances[neighbor] = distances[current] + 1
        queue << neighbor
      end
    end

    puts "Final distances from #{start}:"
    distances.each { |node, dist| puts "#{node}: #{dist}" }
    distances