Cheapest flights within k stops algorithm in JavaScript

Question

The problem:

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

My solution, implemented in JavaScript:

var findCheapestPrice = function(n, flights, src, dst, k) {
    // generate a graph
    let map = new Map();
    for(let i=0; i<flights.length; i++) {
        const [orig, des, cost] = flights[i];
        const temp = map.get(orig) || []
        temp.push([des, cost]);
        map.set(orig, temp);
    }
    
    // start from the source with cost 0
    // [cost, city, available stops]
    let queue = [[0,src,k+1]]
    
    while(queue.length > 0) {
        const [cost, city, stops] = queue.shift();
        if(city === dst)    return cost;    // Get in the destination
        
        // still have available stops
        if(stops > 0) {
            const possibleFlights = map.get(city) || [];
            for(const pf of possibleFlights) {
                // current cost + flight cost
                // decrement stops (one stop to this airport)
                queue.push([cost+pf[1], pf[0], stops-1]);
            }
            
            // Sort by the cheapest next flight (Heap?)
            queue.sort((a,b) => a[0]-b[0]);
        }
    }
    
    // couldn't find a path
    return -1;
};

It works just fine with the basic case tests, but it fails with time limit exceed for the test case below. Is there a way to improve the code?

13
[[11,12,74],[1,8,91],[4,6,13],[7,6,39],[5,12,8],[0,12,54],[8,4,32],[0,11,4],[4,0,91],[11,7,64],[6,3,88],[8,5,80],[11,10,91],[10,0,60],[8,7,92],[12,6,78],[6,2,8],[4,3,54],[3,11,76],[3,12,23],[11,6,79],[6,12,36],[2,11,100],[2,5,49],[7,0,17],[5,8,95],[3,9,98],[8,10,61],[2,12,38],[5,7,58],[9,4,37],[8,6,79],[9,0,1],[2,3,12],[7,10,7],[12,10,52],[7,2,68],[12,2,100],[6,9,53],[7,4,90],[0,5,43],[11,2,52],[11,8,50],[12,4,38],[7,9,94],[2,7,38],[3,7,88],[9,12,20],[12,0,26],[10,5,38],[12,8,50],[0,2,77],[11,0,13],[9,10,76],[2,6,67],[5,6,34],[9,7,62],[5,3,67]]
10
1
10

Answer 1

Refactoring

I have refactored your code to be more understandable. I have mainly extracted what you commented into functions and changed what you had in tuples into objects.

Here is the result:

function generatePossibleFlightsFromCities(flights) {
  const map = {}

  for (let i = 0; i < flights.length; i++) {
    const [origin, destination, cost] = flights[i]
    const destinationsFromOrigin = map[origin] || []
    destinationsFromOrigin.push({
      destination,
      cost
    })
    map[origin] = destinationsFromOrigin
  }

  return map
}

function initiateQueue(src, k) {
  return [{
    cost: 0,
    city: src,
    stops: k + 1
  }]
}

function insertIntoTheQueue(queue, cost, stops, possibleFlight) {
  const totalCost = cost + possibleFlight.cost

  queue.push({
    cost: totalCost,
    city: possibleFlight.destination,
    stops: stops - 1
  });
}

function noMoreStops(stops) {
  return stops === 0
}

function cameToDestination(city, dst) {
  return city === dst
}

function notEmpty(queue) {
  return queue.length > 0
}

function findCheapestFlight(queue, possibleFlightsFromCities, destination) {
  while (notEmpty(queue)) {
    const {
      cost,
      city,
      stops
    } = queue.shift();

    if (cameToDestination(city, destination)) return cost;
    if (noMoreStops(stops)) continue

    const possibleFlights = possibleFlightsFromCities[city]
    for (const possibleFlight of possibleFlights) {
      insertIntoTheQueue(queue, cost, stops, possibleFlight)
    }

    queue.sort((a, b) => a.cost - b.cost);
  }

  return -1
}

const findCheapestPrice = function(n, flights, src, dst, k) {
  let possibleFlightsFromCities = generatePossibleFlightsFromCities(flights)
  let queue = initiateQueue(src, k)

  return findCheapestFlight(queue, possibleFlightsFromCities, dst);
}

This code still has the same problem, but is more readable and easier to understand. The problem still remains as the program still takes too much time.

Solution

You could have tried with the heap, but I do not think it would have solved your problem. The problem is that you simply have too much items in your queue. If you look at your queue you will see something like this:

[{city: 0, cost: 150, stops: 3}, 
..., 
{city: 0, cost: 230, stops: 5}, 
..., 
{city: 0, cost: 270, stops: 5}, 
...
]

Notice, there is nothing wrong with the first one, but look at the second and third one. They stopped exactly the same amount of times, but the second one came there cheaper. This leads to the conclusion that no matter what the third one will always be more expensive, so we can get rid of it - meaning we shouldn't insert it in the queue in the first place. Basically we do not want to try to go somewhere if we can arrive there cheaper by some other path.

The only thing that changes is how we insert the possible flights into the queue:

function cheaperPathToDestinationExists(queue, destination, cost, stops) {
  return queue.some(item => item.city === destination && item.stops === stops && item.cost < cost)
}

function insertIntoTheQueue(queue, cost, stops, possibleFlight) {
  const totalCost = cost + possibleFlight.cost
  if (cheaperPathToDestinationExists(queue, possibleFlight.destination, totalCost, stops - 1)) return

  queue.push({
    cost: totalCost,
    city: possibleFlight.destination,
    stops: stops - 1
  });
}

The solution isn't perfect. There are still some branches that you can cut, but I will leave this up to you to figure out. Also, it is more of a Stack Overflow/Software Engineering question and not a Code Review one.