{ Pathfinding with Graphs. }

Objectives

By the end of this chapter you should be able to:

  • Compare and contrast traversing weighted vs. unweighted graphs
  • Implement more advanced graph traversal algorithms like Dijkstra and A*

Shortest path algorithms are incredibly common when building any application that involves pathfinding. This could be a simple game like pacman or tic tac toe, or something far more complex like building an efficient networking or navigation system.

We will examine two very common algorithms for finding the shortest path, Dijkstra's and A star. If we are trying to find the shortest path between nodes, we need to think about how our adjacency list can account for weights that edges will contain. Right now our implementation of an adjacency list is simply an array of other verticies. However, we need to consider the weights that edges contain so that we can find a path between nodes that has the lowest cost.

// add the node as the key and weight as the value in an object
Graph.prototype.addEdge = function(vertex1, vertex2, weight) {
  this.adjacencyList[vertex1].push({node:vertex2, weight});
  this.adjacencyList[vertex2].push({node:vertex1, weight});
};

Challenge

Now that we have added weights to each edge, re-implement BFS and DFS so that they still work with the new adjacency list. Here is a BFS implementation:

Graph.prototype.BFS = function(start){
  var result = []
  var queue = [start]
  this.adjacencyList[start].visited = true;
  while(queue.length > 0){
    var value = queue.shift();
    result.push(value)
    this.adjacencyList[value].forEach(function(child){
      if(!this.adjacencyList[child.node].visited){
        this.adjacencyList[child.node].visited = true;
        queue.push(child.node)
      }
    }, this)
  }
  return result
}

Dijkstra

The first algorithm we will explore is Dijkstra's algorithm for finding the shortest path. Dijkstra's algorithm was developed by a famous computer scientest Edsger Dijkstra.

Before you continue, watch this and this excellent introduction to Dijkstra's algorithm.

In these videos, you will learn some more about the pseudocode necessary for this algorithm to work as well as the essential data structures necessary to implement this algorithm.

Before we start with the algorithm, we will need to introduce the concept of a priority queue.

Priority Queue

Since we will need to figure out the most optimal nodes to search with this algorithm, we need a data structure that will dynamically adjust to help us figure out which node to visit next. For pathfinding, a priority queue is an optimal data structure. A priority queue works just like a regular queue, but each node placed in the queue has a priority assigned to it and as elements are enqueued, the order of the queue changes based on the priority of the elements. To be more specific, we will be using a min priority queue which will place the values with a lowest cost at the front of the queue.

For these examples we will use a simple object and sort each value.

Implementing Dijkstra

Let's examine the following graph:

https://upload.wikimedia.org/wikipedia/commons/thumb/4/46/Dijkstra_algorithm_1.svg/400px-Dijkstra_algorithm_1.svg.png

Now imagine we want to find the shortest path between vertex S and vertex T. How would we go about calculating that?

The first thing we need to do is assign to every node a distance value and set the current not to 0 and all others to infinity.

Next, we mark this initial node as current and all others as unvisited and enqueue the current node.

We then begin to iterate as long as the queue is not empty. Inside of this loop we dequeue the vertex and get the priority of the node check to see if it has been explored. If it has not been explored, enqueue the adjacent verticies in order of their priority which is the node's priority + the weight of the edge. We then add the node to the list of visited nodes.

// build the graph - https://upload.wikimedia.org/wikipedia/commons/thumb/4/46/Dijkstra_algorithm_1.svg/400px-Dijkstra_algorithm_1.svg.png

g = new Graph
g.addVertex('S')
g.addVertex('P')
g.addVertex('U')
g.addVertex('X')
g.addVertex('Q')
g.addVertex('Y')
g.addVertex('V')
g.addVertex('R')
g.addVertex('W')
g.addVertex('T')

g.addEdge('S','P', 2)
g.addEdge('S','U', 3)

g.addEdge('P','X', 4)
g.addEdge('U','X', 1)

g.addEdge('P','Q', 5)
g.addEdge('U','V', 3)

g.addEdge('X','Q', 7)
g.addEdge('X','Y', 6)
g.addEdge('X','V', 8)

g.addEdge('Q','R', 2)
g.addEdge('Y','R', 1)

g.addEdge('Y','W', 3)
g.addEdge('V','W', 4)

g.addEdge('R','T', 6)
g.addEdge('W','T', 7) // 5 in chart, done so we have different paths

Graph.prototype.Dijkstra = function(nodeA, nodeB) {
  var dist = {}, unvisited = {}, min, tempDist, current, previous = {};

  for (node in this.adjacencyList) {
    unvisited[node] = true;
    previous[node] = undefined;
    node === nodeA ? dist[node] = 0 : dist[node] = Infinity;
  }

  while(unvisited[nodeB]) {
    min = Infinity;
    current = Object.keys(unvisited).reduce(function(acc, node) {
      if (dist[node] < min) {
        acc = node;
        min = dist[node];
      }
      return acc;
    }, undefined);

    delete unvisited[current];

    for (val of this.adjacencyList[current]) {
      if (unvisited[val.node]) {
        unvisited[val.node] = false;
        tempDist = dist[current] + this.adjacencyList[current][this.adjacencyList[current].indexOf(val)].weight
        if (tempDist < dist[val.node]) {
          previous[val.node] = current
          dist[val.node] = tempDist;
        }
      }
    }
  }

  function displayPath(previousPaths, node){
    var paths = [node];
    while(previousPaths[node]){
      paths.unshift(previousPaths[node])
      node = previousPaths[node]
    }
    return paths;
  }

  var path = displayPath(previous, nodeB)

  return [dist[nodeB], path];
};

g.Dijkstra('S','T') // [15, ["S","P","Q","R","T"]]

A*

A star is an extention to Dijkstra's algorithm that includes an additional concept for more efficient pathfinding. This concept is called a heuristic, which we can simply define as a "best guess". Since Dijkstra's will focus on the closest vertex possible, that might not always be the most efficient place to start searching. Imagine that we are trying to figure out the optimal distance from one city to another.

Before you continue, watch this,and this excellent introduction to A*.

With A* we calcualte the cost between two nodes a bit differently and it is expressed by the following terms.

f-cost - the total cost (g-cost + h-cost)
g-cost - our distance cost (exactly the same as what we calculated with Dijkstra)
h-cost - our heuristic cost (an additional cost we add depending on how we calculate our heuristic)

This expression is represented as: f(x) = g(x) + h(x). This means that when we figure out the order of nodes to place in our priority queue, we factor in an additional cost based on a heuristic. So where does this heuristic come from? Simply put, we have to make one up! Fortunately, there are quite a few common heuristics that are used frequently with pathfinding and A*. These two heuristics are the Manhattan Distance (or Taxi Cab Distance) and Euclidian Distance

Manhattan Distance - The Manhattan Distance is the distance between two points measured along axes at right angles. The name alludes to the grid layout of the streets of Manhattan, which causes the shortest path a car could take between two points in the city. You can read more about it here

Euclidian Distance - The Euclidean distance or Euclidean metric is the "ordinary" (i.e. straight-line) distance between two points in Euclidean space. You can read more about it here.

You can think of Euclidian as a straight line between point A and B and Manhattan as a series of right angles (forming a zig-zag). You can read some more about the differences here and here.

For our implementation of A* we will be using the Manhattan Distance, but each heuristic comes with its advantages and disadvantages.

With A* we also keep track of the optimal parent of each node and as the g-cost changes for each node we move to, we may need to "re-parent" the node. You can see this in action here

You can read more about A* here

When you're ready, move on to Graphs Exercises

Continue