我正在将 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))
型
1条答案
按热度按时间mmvthczy1#
通过使用调试器单步执行代码,有几个问题会变得明显:
addRoute
中:this.routes[city] = price
不会执行您想要的操作,因为city
是City
示例,而不是字符串,因此这会将City
对象强制转换为[object Object]
。在JavaScript中,对象键不能是对象。dijkstraShortestPath
为单位:for (let adjacentCity in currentCity.routes)
将读取字符串(因为对象键是字符串),但稍后您将执行if (!visitedCities[adjacentCity.name])
,就好像adjacentCity
是City
对象一样。这样不行。这两个问题是相关的:
City
对象和城市名称是不同的东西,普通对象不能使用City
对象作为键。有很多方法可以解决这个问题。一种方法是在算法中只使用City
对象,而不使用名称(除了生成要返回的名称数组)。您可以使用Map
对象而不是普通对象来为City
对象的集合设置密钥。下面是所有普通对象集合转换为Map(和Set)对象的代码--当然,这会影响代码中的几行代码:
字符串
其他备注
filter
和reduce
的调用扼杀了这个本来很好的算法的效率。而是使用真正的优先级队列。JavaScript本身没有提供一个,但有很多实现可以找到。我还写了一个你可以找到here,在同一个Q&A的其他几个实现中。