undefined value inside the output array.I have tried everything. I've been six hours on this problem. ChatGPT, Copilot Chat all are unable to resolve the issue. It seems that the error comes from this snippet: // ! Visit the next unvisited city with the cheapest price but at this point I have doubts about this.
["Atlanta", "Denver", "Chicago", "El Paso"][ 'Atlanta', undefined, 'El Paso' ]The following is the original Ruby code:
## 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)
Here is my javascript implementation:
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))There are a few issues that become apparent by stepping through the code with a debugger:
In addRoute: this.routes[city] = price will not do what you want, since city is a City instance, not a string, so this casts a City object to [object Object]. In JavaScript, object keys cannot be objects.
In dijkstraShortestPath: for (let adjacentCity in currentCity.routes) will read strings (as object keys are strings), but later you do if (!visitedCities[adjacentCity.name]), as if adjacentCity is a City object. This will not work.
Both issues are related: City objects and city names are different things, and plain objects cannot use City objects as keys. There are many ways to resolve this. One way is to only use City objects in the algorithm, and not the names (except for generating the array of names to be returned). You can use Map objects instead of plain objects to key collections by City objects.
Here is your code with all plain object collections converted to Map (and Set) objects -- of course this impacts more than a few lines in your code:
class City {
constructor(name) {
this.name = name;
this.routes = new Map;
}
addRoute(city, price) {
this.routes.set(city, price);
}
}
// * Dijkstra's Shortest Path Algorithm
function dijkstraShortestPath(startingCity, finalDestination) {
let cheapestPricesTable = new Map;
let cheapestPreviousStopoverCityTable = new Map;
// 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 = new Set;
// Initialize the cheapest prices table with the starting city (the price will be zero since we are already there)
cheapestPricesTable.set(startingCity, 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.add(currentCity);
// 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, price] of currentCity.routes) {
// If we have discovered a new city, we add it to the unvisited cities array
if (!visitedCities.has(adjacentCity)) {
unvisitedCities.push(adjacentCity);
}
// Calculate the price to get to the adjacent city through the current city
let priceThroughCurrentCity =
cheapestPricesTable.get(currentCity) + price;
// If the price from the starting city to the adjacent city is the cheapest so far...
if (!cheapestPricesTable.has(adjacentCity) ||
priceThroughCurrentCity < cheapestPricesTable.get(adjacentCity)
) {
// ...update the two tables
cheapestPricesTable.set(adjacentCity, priceThroughCurrentCity);
cheapestPreviousStopoverCityTable.set(adjacentCity, currentCity);
}
}
// ! Visit the next unvisited city with the cheapest price
currentCity = unvisitedCities.reduce((minCity, city) => {
return cheapestPricesTable.get(city) < cheapestPricesTable.get(minCity) ?
city :
minCity
}, unvisitedCities[0]);
}
// We have completed the core algorithm and can now build the shortest path
let shortestPath = [];
// Start with the final destination
currentCity = finalDestination;
// While we haven't reached the starting city...
while (currentCity !== startingCity) {
// ...add the current city to the shortest path array
shortestPath.push(currentCity.name);
// ...and update the current city to the previous stopover city
currentCity = cheapestPreviousStopoverCityTable.get(currentCity);
}
// 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));Please terminate statements with a semicolon in JavaScript. Although there is automatic semicolon insertion, it is better to not leave it to that algorithm and take control of it yourself. You wouldn't be the first to fall for its traps.
Dijkstra's algorithm is not efficient when you use a plain array as priority queue. The calls to filter and reduce kill the efficiency of this otherwise good algorithm. Instead use a true priority queue. JavaScript doesn't offer one natively, but there are many implementations to find. I also wrote one which you can find here, amidst several other implementations on the same Q&A.