我正在将 Dijkstra shortest path between cities 算法从Ruby转换为JavaScript，并在输出数组中获得undefined值。

我什么都试过了。我花了六个小时在这个问题上。ChatGPT、Copilot Chat均无法解决此问题。这个错误似乎来自这个片段：// ! Visit the next unvisited city with the cheapest price但在这一点上我有疑问。

• 正确输出：["Atlanta", "Denver", "Chicago", "El Paso"]个
• 我的错误：[ 'Atlanta', undefined, 'El Paso' ]

以下是原始的Ruby代码：

## City class:

class City
  attr_accessor :name, :routes

  def initialize(name)
    @name = name
    @routes = {}
  end

  def add_route(city, price)
    @routes[city] = price
  end
end

## Dijkstra's Algorithm:

def dijkstra_shortest_path(starting_city, final_destination)
  cheapest_prices_table = {}
  cheapest_previous_stopover_city_table = {}

  # To keep our code simple, we'll use a basic array to keep track of
  # the known cities we haven't yet visited:
  unvisited_cities = []

  # We keep track of the cities we've visited using a hash table. 
  # We could have used an array, but since we'll be doing lookups,
  # a hash table is more efficient:
  visited_cities = {}

  # We add the starting city's name as the first key inside the 
  # cheapest_prices_table. It has a value of 0, since it costs nothing
  # to get there:
  cheapest_prices_table[starting_city.name] = 0

  current_city = starting_city

  # This loop is the core of the algorithm. It runs as long as we can 
  # visit a city that we haven't visited yet:
  while current_city

    # We add the current_city's name to the visited_cities hash to record
    # that we've offiically visited it. We also remove it from the list
    # of unvisited cities:
    visited_cities[current_city.name] = true
    unvisited_cities.delete(current_city)

    # We iterate over each of the current_city's adjacent cities:
    current_city.routes.each do |adjacent_city, price|

      # If we've discovered a new city, 
      # we add it to the list of unvisited_cities:
      unvisited_cities << 
        adjacent_city unless visited_cities[adjacent_city.name]

      # We calculate the price of getting from the STARTING city to the
      # ADJACENT city using the CURRENT city as the second-to-last stop:
      price_through_current_city = 
        cheapest_prices_table[current_city.name] + price

      # If the price from the STARTING city to the ADJACENT city is 
      # the cheapest one we've found so far...
      if !cheapest_prices_table[adjacent_city.name] ||
       price_through_current_city < cheapest_prices_table[adjacent_city.name]

        # ... we update our two tables:
        cheapest_prices_table[adjacent_city.name] = price_through_current_city
        cheapest_previous_stopover_city_table[adjacent_city.name] = 
          current_city.name
      end
    end

    # 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

  # We have completed the core algorithm. At this point, the
  # cheapest_prices_table contains all the cheapest prices to get to each
  # city from the starting city. However, to calculate the precise path
  # to take from our starting city to our final destination, we need to move on.

  # We'll build the shortest path using a simple array:
  shortest_path = []
  
  # To construct the shortest path, we need to work backwards from our 
  # final destination. So we begin with the final destination as our 
  # current_city_name:
  current_city_name = final_destination.name

  # We loop until we reach our starting city:
  while current_city_name != starting_city.name

    # We add each current_city_name we encounter to the shortest path array:
    shortest_path << current_city_name
    # We use the cheapest_previous_stopover_city_table to follow each city
    # to its previous stopover city:
    current_city_name = cheapest_previous_stopover_city_table[current_city_name]
  end

  # We cap things off by adding the starting city to the shortest path:
  shortest_path << starting_city.name

  # We reverse the output so we can see the path from beginning to end:
  return shortest_path.reverse
end

atlanta = City.new("Atlanta")
boston = City.new("Boston")
chicago = City.new("Chicago")
denver = City.new("Denver")
el_paso = City.new("El Paso")

atlanta.add_route(boston, 100)
atlanta.add_route(denver, 160)
boston.add_route(chicago, 120)
boston.add_route(denver, 180)
chicago.add_route(el_paso, 80)
denver.add_route(chicago, 40)
denver.add_route(el_paso, 140)

p dijkstra_shortest_path(atlanta, el_paso)

字符串
下面是我的JavaScript实现：

class City {
  constructor(name) {
    this.name = name
    this.routes = {}
  }

  addRoute(city, price) {
    this.routes[city] = price
  }
}

// * Dijkstra's Shortest Path Algorithm
function dijkstraShortestPath(startingCity, finalDestination) {
  let cheapestPricesTable = {}
  let cheapestPreviousStopoverCityTable = {}

  // Keep track of known cities we haven't visited yet
  let unvisitedCities = []

  // Keep track of cities we have visited using a hash table
  let visitedCities = {}

  // Initialize the cheapest prices table with the starting city (the price will be zero since we are already there)
  cheapestPricesTable[startingCity.name] = 0

  // Initialize the current city to the starting city
  let currentCity = startingCity

  // While there is a current city
  while (currentCity) {
    // Mark the current city as visited
    visitedCities[currentCity.name] = true

    // Delete the current city from the unvisited cities array
    unvisitedCities = unvisitedCities.filter((city) => city !== currentCity)

    // Iterate over each current city's adjacent cities
    for (let adjacentCity in currentCity.routes) {
      // Get the price to get to the adjacent city from the current city
      let price = currentCity.routes[adjacentCity]
      // If we have discovered a new city, we add it to the unvisited cities array
      if (!visitedCities[adjacentCity.name]) {
        unvisitedCities.push(adjacentCity)
      }

      // Calculate the price to get to the adjacent city through the current city
      let priceThroughCurrentCity =
        cheapestPricesTable[currentCity.name] + price

      // If the price from the starting city to the adjacent city is the cheapest so far...
      if (!cheapestPricesTable[adjacentCity.name] ||
        priceThroughCurrentCity < cheapestPricesTable[adjacentCity.name]
      ) {
        // ...update the two tables
        cheapestPricesTable[adjacentCity.name] = priceThroughCurrentCity
        cheapestPreviousStopoverCityTable[adjacentCity.name] = currentCity.name
      }
    }

    // ! Visit the next unvisited city with the cheapest price
    currentCity = unvisitedCities.reduce((minCity, city) => {
      return cheapestPricesTable[city.name] < cheapestPricesTable[minCity.name] ?
        city :
        minCity
    }, unvisitedCities[0])
  }

  // We have completed the core algorithm and can now build the shortest path
  let shortestPath = []

  // Start with the final destination
  let currentCityName = finalDestination.name

  // While we haven't reached the starting city...
  while (currentCityName !== startingCity.name) {
    // ...add the current city to the shortest path array
    shortestPath.push(currentCityName)

    // ...and update the current city to the previous stopover city
    currentCityName = cheapestPreviousStopoverCityTable[currentCityName]
  }

  // Finally, add the starting city to the shortest path array
  shortestPath.push(startingCity.name)

  // Return the shortest path array in reverse order
  return shortestPath.reverse()
}

// ------------------------------

let atlanta = new City('Atlanta')
let boston = new City('Boston')
let chicago = new City('Chicago')
let denver = new City('Denver')
let elPaso = new City('El Paso')

atlanta.addRoute(boston, 100)
atlanta.addRoute(denver, 160)
boston.addRoute(chicago, 120)
boston.addRoute(denver, 180)
chicago.addRoute(elPaso, 80)
denver.addRoute(chicago, 40)
denver.addRoute(elPaso, 140)

console.log(dijkstraShortestPath(atlanta, elPaso))

型