Dijkstra shortest path between cities implementation

Question

I am converting a Dijkstra shortest path between cities algorithm from Ruby to Javascript and I am getting `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.

Correct output: ["Atlanta", "Denver", "Chicago", "El Paso"]
My Error: [ '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))

score 1 · Accepted Answer · answered Jul 20 '23 at 08:57

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));

Other remarks

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.

Thank you so much for your detailed answer! Now it works perfectly. — Chris Faux, Jul 21 '23 at 04:20

Dijkstra shortest path between cities implementation

I am converting a Dijkstra shortest path between cities algorithm from Ruby to Javascript and I am getting undefined value inside the output array.

1 Answers1

Other remarks

I am converting a Dijkstra shortest path between cities algorithm from Ruby to Javascript and I am getting `undefined` value inside the output array.