Advanced Graph Algorithms

Welcome to this insightful practice-based lesson! Today, we are immersing ourselves in Advanced Graph Algorithms. This is a crucial topic in computer science as graphs are prevalent in numerous real-world situations, from social networks to computer networks.

Understanding how to traverse, search, and optimize graphs is essential, particularly when it involves finding the shortest path between nodes, mapping routes, or determining any associations between specific data points. In Ruby, this involves leveraging data structures like hashes to represent graphs and understanding how to efficiently manage and manipulate these data structures. Let's dive in!

One of the exciting algorithms we'll be examining is Dijkstra’s Algorithm. Named after its Dutch computer scientist inventor, Dijkstra's algorithm is fundamental for finding the shortest path in a graph with non-negative weights. In Ruby, we don’t have a built-in binary heap, but we can use the Ruby gem pqueue to implement a priority queue.

Here is how you can implement Dijkstra’s algorithm in Ruby:

require 'pqueue'

def dijkstra(graph, start)
  # Initialize distances with the starting node at 0 distance
  dist = { start => 0 }
  # Hash to keep track of visited nodes
  visited = {}

  # Priority queue storing pairs of [distance, node], sorted by distance
  min_heap = PQueue.new([[0, start]]) { |a, b| a[0] < b[0] }

  # Process nodes until the priority queue is empty
  until min_heap.empty?
    # Pop the node with the smallest distance
    current_dist, u = min_heap.pop
    next if visited[u]  # Skip if the node is already visited
    visited[u] = true

    # Iterate through each neighbor of the current node
    graph[u].each do |v, weight|
      # Calculate the potential new distance to the neighbor
      distance = current_dist + weight
      # If this new distance is shorter, update and add to the queue
      if distance < dist.fetch(v, Float::INFINITY)
        dist[v] = distance
        min_heap.push([distance, v])
      end
    end
  end
  dist
end

# Define the graph as an adjacency list with node distances
graph = {
  'A' => { 'B' => 1, 'C' => 4 },
  'B' => { 'A' => 1, 'C' => 2, 'D' => 5 },
  'C' => { 'A' => 4, 'B' => 2, 'D' => 1 },
  'D' => { 'B' => 5, 'C' => 1 }
}

puts dijkstra(graph, 'A')  # Output: {"A"=>0, "B"=>1, "C"=>3, "D"=>4}

This code implements Dijkstra's algorithm in Ruby to find the shortest path from a starting node to all other nodes in a weighted graph. The algorithm uses a priority queue (PQueue) to efficiently retrieve the node with the smallest distance at each step, ensuring the shortest path is found by progressively visiting each node's neighbors and updating the shortest distance as needed.