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 vertices. 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 scientist 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.

Priority Queues are commonly implemented using Binary Heaps so if you have not done that yet, make sure you have that implemented before trying these next algorithms!

Implementing Dijkstra

Let's examine the following graph:

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

We'll need to make a couple objects to store visited vertices and distances between vertices.

The first thing we need to do is assign to every node a distance value and set the current node to 0 and all others to infinity. Even though we might know the distances by looking at the graph, we're going to imagine that we know nothing about distances except for the node we are starting at. So we first loop over each vertex and unless the vertex is the starting node, we place a key of that vertex and a value of Infinity in the distances object.

In each iteration, we also enqueue each node with the priority of zero if it is the start node or Infinity if it is another node.

Finally, in each iteration, we initialize a key of the vertex and a value of null in our previous object. The idea here is that we have not visited any nodes yet so there are no "previous" nodes visited. This object, along with our distances object will be updated.

We then begin to iterate as long as the queue is not empty. Inside of this loop we dequeue the vertex first check to see if the vertex we have dequeued is the node we are trying to visit, if this is true, it means we are done iterating and we find our shortest path.

One way to do that would be to build an array and iterate through our previous object. We can backtrack using our previous object to find the path that got us to the final vertex. Once we have found this path we can return it and we're done!

What happens if the vertex we have dequeued is not the final node? The fun part! We need to examine each edge for this vertex and calculate the distance from our starting node. If the distance from our starting node is less than what we currently have in our distances object for that vertex we are checking, we will have to do a few things.

First, we need to update the distances object for that vertex with the new, shorter distance. We also need to update our previous object for that vertex with the node we just enqueued. Finally, we need to enqueue the vertex with the updated weight.

This is quite a lot, so try to watch the video above and build a table of previously visited nodes and distances between nodes - it will help quite a bit.

A*

A star is an extension 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 calculate 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