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
}

You’re right that this bit of code can be confusing - it relies on a special feature that is available in Ruby’s min method. Here, unvisited_cities.min do |city| iterates through all the City instances within the unvisited_cities array, and checks each one against the cheapest_prices_table. That is, it looks up each City in that table by its key and finds its corresponding value. Once it has all the values, min selects the City with the lowest value.

Perhaps in a future version, I can make this code clearer. Thanks for your input!

Thank you for the explanation! I was really struggling to understand what was happening here. I’ll have to play around with it to see that in action, but now I have a pretty good grasp of the idea.