You are browsing the archive for Breath First.

[JavaScript Quiz #16] Smallest number of flights

August 15, 2015 in JavaScript, Quiz

Consider you have a set of places (CAI, FRA, MAD, NYC, SFO) and there are available flights between some of these destinations as shown below.

CAI -> FRA
FRA -> MAD
MAD -> NYC
CAI -> MAD
NYC -> SFO
FRA -> CAI
MAD -> FRA

Design and develop a JavaScript function that can get the shortest possible path from a destination X to destination Y if there is any.
.
.
.
.
.
.
.
.
.
.
.
.
.
In order to develop a JavaScript function which can get the shortest path between two destinations, first of all, we need to think about the proper data structure which can represent these places and the connections between them. If we think about it, we will find that these placed can be represented as nodes and the connections between these places can be represented as edges which is typically a Graph. We can represent this Graph as a 2D N X N array as shown below.

    CAI FRA MAD NYC SFO
CAI  0   1   1   0   0
FRA  1   0   1   0   0
MAD  0   1   0   1   0
NYC  0   0   0   0   1
SFO  0   0   0   0   0

The previous matrix can be translated to the following JavaScript code.

var mapping = {
    "CAI": 0,
    "FRA": 1,
    "MAD": 2,
    "NYC": 3,
    "SFO": 4
};

var routeGraph = 
[
    [0, 1, 1, 0, 0],
    [1, 0, 1, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0]    
];

After make the proper representation, we need to think about how to get the shortest path between any two nodes in this unweighted graph. Since this graph is unweighted, we can use directly BFS (Breath First Search) in order to get the shortest path. For more information about BFS, check: https://en.wikipedia.org/wiki/Breadth-first_search.

In order to implement BFS, there are some notes for our implementation below:

  1. We utilized the Queue data structure for storing the nodes in a first-in, first-out (FIFO) style, we explore the oldest unexplored nodes first. Thus our explorations radiate out slowly from the starting node, defining a breadth-first search.
  2. In order to keep track of the shortest path, we have a JavaScript map nodeParent object which stores the first visited parent of the current visited node.
  3. Finally, when the search finds the destination then we construct the final path from the nodeParent object and stores it in the finalPath array.

The code below shows our BFS implementation in order to get the shortest path between the start and destination nodes.

var ShortestPathFinder = function() {
}

ShortestPathFinder.find = function (start, destination) {
    var visited = {}; // A map containing all of the visited nodes ...
    var nodeParent = {}; // An map containing the node parents ...
    var queue = [start], i, found = false, finalPath = [], neighbours = [];    
    
    nodeParent[start] = null;
    
    var current = queue.shift();
    
    while ((neighbours = ShortestPathFinder.getNeighbours(current)) != null) {
    
        for (i = 0; i < neighbours.length; ++i) {
            
            // If we find the destination then exit these loops ...
            if (neighbours[i] == destination) {
                found = true;
                nodeParent[neighbours[i]] = current;
                break;
            }
        
            if (! visited[neighbours[i]]) {
                
                // Mark this node as "visited" ...
                visited[neighbours[i]] = true;
            
                // Add element to the queue ...
                queue.push(neighbours[i]);
                nodeParent[neighbours[i]] = current;
            }
        }
        
        if (queue.length == 0) {
            break;
        }
        
        current = queue.shift();
    }
    
    if (! found) {
        console.error("No path is found between " + start + " and " + destination);
        
        return null;
    }
    
    // Construct the final path from the node parent map ...
    current = destination;
    
    finalPath.push(destination);
    
    while (nodeParent[current] != start) {
        finalPath.push(nodeParent[current]);
        
        current = nodeParent[current];
    }
    
    finalPath.push(start);    
    
    return finalPath.reverse();
}

In order to get the neighbours of the current node, a simple function is implemented to get the neighbours from the routeGraph matrix as follows.

ShortestPathFinder.getNeighbours = function(current) {
    var currentIndex = mapping[current], i, result = [];
    
    for (i = 0; i < routeGraph[currentIndex].length; ++i) {
        if (routeGraph[currentIndex][i] == 1) {
            result.push(mapping.getKey(i));
        }
    }
    
    return result;
}

Finally, we can test our developed JavaScript function by having the following test cases.

console.log(ShortestPathFinder.find("CAI", "NYC"));
console.log(ShortestPathFinder.find("CAI", "SFO"));
console.log(ShortestPathFinder.find("FRA", "NYC"));
console.log(ShortestPathFinder.find("SFO", "CAI"));
console.log(ShortestPathFinder.find("MAD", "CAI"));

Below is the output of the console.

["CAI", "MAD", "NYC"]
["CAI", "MAD", "NYC", "SFO"]
["FRA", "MAD", "NYC"]
No path is found between SFO and CAI
null
["MAD", "FRA", "CAI"]

Attached below, the complete solution code for your reference, if you have comments or a better solution, feel free to comment below.

/*
CAI -> FRA
FRA -> MAD
MAD -> NYC
CAI -> MAD
NYC -> SFO
FRA -> CAI
MAD -> FRA

    CAI FRA MAD NYC SFO
CAI  0   1   1   0   0
FRA  1   0   1   0   0
MAD  0   1   0   1   0
NYC  0   0   0   0   1
SFO  0   0   0   0   0
*/

var mapping = {
    "CAI": 0,
    "FRA": 1,
    "MAD": 2,
    "NYC": 3,
    "SFO": 4
};

var routeGraph = 
[
    [0, 1, 1, 0, 0],
    [1, 0, 1, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0]    
];

Object.prototype.getKey = function(value){
  for(var key in this){
    if(this[key] == value){
      return key;
    }
  }
  return null;
};


var ShortestPathFinder = function() {
}

ShortestPathFinder.find = function (start, destination) {
    var visited = {}; // A map containing all of the visited nodes ...
    var nodeParent = {}; // An map containing the node parents ...
    var queue = [start], i, found = false, finalPath = [], neighbours = [];    
    
    nodeParent[start] = null;
    
    var current = queue.shift();
    
    while ((neighbours = ShortestPathFinder.getNeighbours(current)) != null) {
    
        for (i = 0; i < neighbours.length; ++i) {
            
            // If we find the destination then exit these loops ...
            if (neighbours[i] == destination) {
                found = true;
                nodeParent[neighbours[i]] = current;
                break;
            }
        
            if (! visited[neighbours[i]]) {
                
                // Mark this node as "visited" ...
                visited[neighbours[i]] = true;
            
                // Add element to the queue ...
                queue.push(neighbours[i]);
                nodeParent[neighbours[i]] = current;
            }
        }
        
        if (queue.length == 0) {
            break;
        }
        
        current = queue.shift();
    }
    
    if (! found) {
        console.error("No path is found between " + start + " and " + destination);
        
        return null;
    }
    
    // Construct the final path from the node parent map ...
    current = destination;
    
    finalPath.push(destination);
    
    while (nodeParent[current] != start) {
        finalPath.push(nodeParent[current]);
        
        current = nodeParent[current];
    }
    
    finalPath.push(start);    
    
    return finalPath.reverse();
}

ShortestPathFinder.getNeighbours = function(current) {
    var currentIndex = mapping[current], i, result = [];
    
    for (i = 0; i < routeGraph[currentIndex].length; ++i) {
        if (routeGraph[currentIndex][i] == 1) {
            result.push(mapping.getKey(i));
        }
    }
    
    return result;
}

console.log(ShortestPathFinder.find("CAI", "NYC"));
console.log(ShortestPathFinder.find("CAI", "SFO"));
console.log(ShortestPathFinder.find("FRA", "NYC"));
console.log(ShortestPathFinder.find("SFO", "CAI"));
console.log(ShortestPathFinder.find("MAD", "CAI"));
Skip to toolbar