samples/13_path_finding_algorithms/05_dijkstra/app/main.rb
def calc_dijkstra
    # The initial values for the Dijkstra search
    dijkstra_search.frontier                << [state.star, 0]
    dijkstra_search.came_from[state.star]   = nil
    dijkstra_search.cost_so_far[state.star] = 0

    # Until their are no more cells to be explored
    until dijkstra_search.frontier.empty?
      # Get the next cell to be explored from
      # We get the first element of the array which is the cell. The second element is the priority.
      current = dijkstra_search.frontier.shift[0]

      # Stop the search if we found the target
      return if current == state.target

      # For each of the neighbors
      adjacent_neighbors(current).each do | neighbor |
        # Unless this cell is a wall or has already been explored.
        unless dijkstra_search.came_from.has_key?(neighbor) or state.walls.has_key?(neighbor)
          # Calculate the movement cost of getting to this cell and memo
          new_cost = dijkstra_search.cost_so_far[current] + cost(neighbor)
          dijkstra_search.cost_so_far[neighbor] = new_cost

          # Add this neighbor to the cells too be explored
          dijkstra_search.frontier << [neighbor, new_cost]
          dijkstra_search.came_from[neighbor] = current
        end
      end

      # Sort the frontier so exploration occurs that have a low cost so far.
      # My implementation of a priority queue
      dijkstra_search.frontier = dijkstra_search.frontier.sort_by {|cell, priority| priority}
    end
  end
# Calculates the Dijkstra Search from the beginning to the end
Calculates the Dijkstra Search from the beginning to the end
Calculates the Dijkstra Search from the beginning to the end
def calc_dijkstra
    dijkstra_search.frontier                << [state.star, 0]
    dijkstra_search.came_from[state.star]   = nil
    dijkstra_search.cost_so_far[state.star] = 0
    until dijkstra_search.frontier.empty?
      current = dijkstra_search.frontier.shift[0]
      return if current == state.target
      adjacent_neighbors(current).each do | neighbor |
        unless dijkstra_search.came_from.has_key?(neighbor) or state.walls.has_key?(neighbor)
          new_cost = dijkstra_search.cost_so_far[current] + cost(neighbor)
          dijkstra_search.cost_so_far[neighbor] = new_cost
          dijkstra_search.frontier << [neighbor, new_cost]
          dijkstra_search.came_from[neighbor] = current
        end
      end
      dijkstra_search.frontier = dijkstra_search.frontier.sort_by {|cell, priority| priority}
    end
  end
def calc_dijkstra dijkstra_search . frontier << [ state . star , 0 ] dijkstra_search . came_from [ state . star ] = nil dijkstra_search . cost_so_far [ state . star ] = 0 until dijkstra_search . frontier . empty? current = dijkstra_search . frontier . shift [ 0 ] return if current == state . target adjacent_neighbors ( current ) . each do | neighbor | unless dijkstra_search . came_from . has_key? ( neighbor ) or state . walls . has_key? ( neighbor ) new_cost = dijkstra_search . cost_so_far [ current ] + cost ( neighbor ) dijkstra_search . cost_so_far [ neighbor ] = new_cost dijkstra_search . frontier << [ neighbor , new_cost ] dijkstra_search . came_from [ neighbor ] = current end end dijkstra_search . frontier = dijkstra_search . frontier . sort_by { | cell , priority | priority } end end
Calculates the Dijkstra Search from the beginning to the end
Calculates the Dijkstra Search from the beginning to the end
# The initial values for the Dijkstra search # Until their are no more cells to be explored # Get the next cell to be explored from # We get the first element of the array which is the cell. The second element is the priority. # Stop the search if we found the target # For each of the neighbors # Unless this cell is a wall or has already been explored. # Calculate the movement cost of getting to this cell and memo # Add this neighbor to the cells too be explored # Sort the frontier so exploration occurs that have a low cost so far. # My implementation of a priority queue