A Common-Sense Guide to Data Structures and Algorithms, Second Edition: Dijkstra code syntax question (page 379)

On page 379, this part of the Dijkstra shortest path code is supposed to determine the next unvisited city to visit based on it being the cheapest to get to from the starting city:

    # We visit our next unvisited city. We choose the one that is cheapest
    # to get to from the STARTING city:
    current_city = unvisited_cities.min do |city|
      cheapest_prices_table[city.name]
    end
  end

I don’t understand this syntax; is anyone able to explain how this works?
unvisited_cities is an array of City objects and .min cannot be directly applied to this array.
And apparently “unvisited_cities.min do |city|” is different from something like “unvisited_cities.each do |city|”?
Is anyone able to walk me through what this bit of code does/how it works? I’m not understanding how this determines the cheapest unvisited city.

Thank you!

1 Like

@jaywengrow

This is confusing to me as well. As mentioned by OP, this array doesn’t store price information, so how can we use ruby’s min method here?

@pjd

Hey, I’m using Go. Go tends to be a little more explicit, so it might help you. (or not :wink: )

I ended up just writing a separate func to get the city with the lowest price from the origin as below:

// cheapestCityFromOrigin finds the city with the cheapest flight from the origin.
// This is needed because this implementation doesn't use a heap.
func cheapestCityFromOrigin(unvisitedCities []*City, cheapestPrices map[string]int) *City {
	if len(unvisitedCities) <= 0 {
		return nil
	}

	cheapestCity := unvisitedCities[0]
	lowestPrice := cheapestPrices[unvisitedCities[0].name]

	for i := 1; i < len(unvisitedCities); i++ {
		if cheapestPrices[unvisitedCities[i].name] < lowestPrice {
			cheapestCity = unvisitedCities[i]
            lowestPrice = cheapestPrices[unvisitedCities[i].name]
		}
	}

	return cheapestCity
}