Dijkstra Algorithm in Ruby

dijkstra_algorithm.rb

=begin
  Implement dijkstra's algorithm

  reference
  https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

  V is the number of vertices
  N is the maximum number of edges attached to a single node.

  Time complexity: O( V * N * log V)
  Space complexity: O(N)
=end

# Find a hash that showing from stat_node to any nodes in the graph with minimum cost
#
# @params graph[Array<Hash>]
# @params node[Fixnum]
# @returns [Hash] {:node => min cost from start node to node}
def dijkstra_algorithm(graph, weight, start_node)
  min_cost_from_start_to_nodes = {start_node => 0}
  sorted_nodes_by_cost         = [start_node]
  walked_nodes                 = {}

  while sorted_nodes_by_cost.any?
    lowest_cost_node               = sorted_nodes_by_cost.shift
    walked_nodes[lowest_cost_node] = true
    adjant_nodes                   = graph[lowest_cost_node]

    adjant_nodes.each do |node|
      next if walked_nodes.key?(node)

      weight_cost       = weight[weight_key(lowest_cost_node, node)]
      node_to_node_cost = min_cost_from_start_to_nodes[lowest_cost_node] + weight_cost

      if min_cost_from_start_to_nodes[node].nil? ||
        min_cost_from_start_to_nodes[node] > node_to_node_cost
        min_cost_from_start_to_nodes[node] = node_to_node_cost
      end

      sorted_nodes_by_cost = binary_insert(sorted_nodes_by_cost, node, min_cost_from_start_to_nodes)
    end
  end

  min_cost_from_start_to_nodes
end

# Insert element into sorted array with O(log n) time complexity and insert
# it into the array
#
# @params array [Array]
# @params element [Fixnum]
# @params cost [Hash] {element => cost of edge}
def binary_insert(array, element, cost)
  insert_index = binary_search(array, element, cost, 0, array.size - 1)

  array[0...insert_index] + [element] + array[insert_index..-1]
end

def binary_search(array, element, cost, left, right)
  return left if left >= right

  mid = ((left + right) / 2.0).floor

  if cost[array[mid]] > cost[element]
    binary_search(array, element, cost, left, mid - 1)
  elsif cost[array[mid]] < cost[element]
    binary_search(array, element, cost, mid + 1, right)
  else
    mid
  end
end

# Return the weight key of weight hash
def weight_key(node1, node2)
  left  = [node1, node2].min
  right = [node1, node2].max
  [left, right]
end

graph = {
  1 => [2,3,6],
  2 => [1,3,4],
  3 => [1,2,4,6],
  4 => [2,3,5],
  5 => [4,6],
  6 => [1,3,5]
}

weight = {
  [1,2] => 7,
  [1,3] => 9,
  [1,6] => 14,
  [2,3] => 10,
  [2,4] => 15,
  [3,4] => 11,
  [3,6] => 2,
  [4,5] => 6,
  [5,6] => 9
}

print dijkstra_algorithm(graph, weight, 1)
puts