Dijkstra's Algorithm (with comments)

dijkstra_with_comments.rb

# Define a graph using an adjacency list
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 }
}

# Define the dijkstra method to find the shortest path from a start node
def dijkstra(graph, start)
  # Initialize a hash to store the shortest distance from start node to every other node
  distances = {}
  # Initialize a hash to keep track of which nodes have been visited
  visited = {}
  # Extract all node keys (names) from the graph to work with
  nodes = graph.keys

  # Set the initial distance to each node as infinity (unknown distance)
  nodes.each { |node| distances[node] = Float::INFINITY }
  # The distance from the start node to itself is always 0
  distances[start] = 0

  # Iterate until all nodes have been visited
  until nodes.empty?
    # Find the unvisited node with the smallest distance
    min_node = nodes.min_by { |node| visited[node] ? Float::INFINITY : distances[node] }

    # If the smallest distance is infinity, the remaining nodes are unreachable, so break out of the loop
    break if distances[min_node] == Float::INFINITY

    # For each neighbor of the current node, calculate the distance from the start node
    graph[min_node].each do |neighbor, value|
      alt = distances[min_node] + value # Calculate tentative distance to neighbor
      # If the newly calculated distance is shorter, update the shortest distance for this neighbor
      distances[neighbor] = alt if alt < distances[neighbor]
    end

    # Mark the current node as visited
    visited[min_node] = true
    # Remove this node from the list of nodes to be visited
    nodes.delete(min_node)
  end

  # Return the shortest distances from the start node to all other nodes
  distances
end

# Test the dijkstra function with 'A' as the starting point
puts dijkstra(graph, 'A')