Essential Graph Theory: Finding the Shortest Path

Spike Burton
Jul 7, 2019 · 7 min read
Image for post
Image for post
Photo by Clint Adair on Unsplash

In modern programming and computer science, graphs are arguably one of the most prevalent data structures present in the real world. Unlike the graphs you may be familiar with which visually represent quantitative data, a graph in computer science is a data structure that represents the relationships between various nodes of data. A tree is a special type of graph which most web programmers are familiar with by way of interacting with the DOM: every node has only one parent node, and may have multiple children nodes. A common example might be a div containing an h1 header as well as an unordered list. The unordered list has many li elements, which are its children. In this example the div is a parent to both the header and the list, while the list is also a parent and has many children.

Graphs are not limited to tree structures, however. Nodes may be connected to other nodes in any fashion with no clear start or endpoint. A common example of a graph in the modern web might be a social network:

Image for post
Image for post

While referring to a graph, each node is also known as a vertex, while the connection between two nodes is called an edge. It is worth noting that there are two types of graphs in terms of the relationships between nodes. In a directed graph, each edge has a direction, and may be either unidirectional or bidirectional. By contrast, in an undirected graph, every edge is bidirectional. An example of a social network which can be represented by a directed graph is Twitter: you may follow Kim Kardashian West, but Kim may or may not follow you back. On the other hand, Facebook relationships are an example of an undirected graph: once the friendship request has been accepted, each person is subscribed to the feed of the other.

Besides direction, an edge may also have magnitude. In this occasion, the graph is referred to as a weighted graph. A common example of a weighted graph would be a street map: the intersection points between roads would be the vertices, while the roads themselves would be the edges. the distance between two intersection points would be the weight of that edge. This scenario brings up an interesting problem: given point A and point B on the map, what is the shortest route to get from A to B, when there are multiple possible routes? This is exactly the problem we will aim to solve.

Commonly referred to as Dijkstra’s Algorithm, this problem was famously first solved by Dutch programmer Edsger W. Dijkstra in 1956. For the sake of simplicity, we will consider the solution for an undirected weighted graph. This translates into an assumption that there are no one-way streets within the map. Let’s focus on finding the fastest route from point A to point E on the following graph:

Image for post
Image for post
Created using draw.io

Starting from point A, traversing through point B leads directly to point E, with a distance of 7. However, the shortest route is actually traversing through nodes C, D, F and E, with a distance of 6. So, how do we go about figuring out what the shortest path is?

As Dijkstra concluded, the solution involves visiting every node (starting with the node that is the shortest distance away), and keeping track of the shortest distance to that node from the starting node. If this distance is smaller than the distance previously recorded, then a few things need to happen. First, this new distance must be recorded as the known shortest distance. Also, we must keep a history of the path to get to the neighbor node, and so log the current node in the history. Finally, we must next visit all of the nodes connected to the neighboring node that have not yet been visited. We must then pick the next node to visit, which should again be the node that is the shortest distance away.

Now that we have discussed and outlined a solution, let’s talk about how an implementation will work. First, we need a way to represent our graph as data. Although there are multiple ways to do this, for our purposes we will build an adjacency list. We will use an object (or hash map) to keep track of each node’s neighbors, as well as their distances from that node, as follows:

const adjList = {
'a': [{node: 'b', weight: 4},{node: 'c', weight: 2}],
'b': [{node: 'a', weight: 4},{node: 'e', weight: 3}],
'c': [{node: 'a', weight: 2},{node: 'd', weight: 2},
{node: 'f', weight: 4}],
'd': [{node: 'c', weight: 2},{node: 'e', weight: 3},
{node: 'f', weight: 1}],
'e': [{node: 'b', weight: 3},{node: 'd', weight: 3},
{node: 'f', weight: 1}],
'f': [{node: 'c', weight: 4},{node: 'd', weight: 1},
{node: 'e', weight: 1}]
};

For each node in the adjacency list, we are storing an array with the relevant data for each of its neighboring nodes. Now that we have a way to represent our graph, we next need to figure out how to find the closest neighbor for any given node. For this, we will use a priority queue. When we visit a node, we will enqueue all of its neighbors to visit next, where the queue is ordered with the smallest element at the front. For the sake of simplicity, we can implement this as follows:

class PriorityQueue {
constructor() {
this.values = [];
}
enqueue(value, priority) {
this.values.push({
value,
priority
});
this.values.sort((a, b) => a.priority - b.priority);
}
dequeue() {
return this.values.shift();
}
}

Although this is less than optimal, it will serve our purposes here. If you would like to see an implementation of the priority queue using a binary heap, which is more optimal in terms of time complexity, please refer to the code accompanying this post.

With most of the setup out of the way, there are just a few more things to discuss. First, we will need to keep track of the shortest distance to every node visited so far. In order to do this, we will just use an object literal. We will initialize every node with a distance of Infinity, except for the starting node, which will have a distance of 0. We will also keep a history of the nodes visited so far in order, also using an object, where each value is initialized to null. We will also need to enqueue the starting node to visit first with a priority of 0, and every other node with a priority of Infinity. So far, our code should look like this:

function shortestPath(start, end) {
const pq = new PriorityQueue();
const history = {}, distances = {};
for (let key in adjList) {
if (key === start) {
pq.enqueue(key, 0);
distances[key] = 0;
} else {
pq.enqueue(key, Infinity);
distances[key] = Infinity;
}
history[key] = null;
}
}

Next, we will need to visit each node in the queue, and calculate the distances to each of its neighbors. If the distance to that node by following the current route is less than the distance that has already been recorded, we will update the distance, update the history, and enqueue that node to visit next. Note that if we dequeue the end node, we are done, since we took the shortest path to get there. Inside of our function after the for loop, let’s add the following:

while (pq.values.length > 0) {
let cur = pq.dequeue().value;
if (cur === v2) break;
for (let neighbor of adjList[cur]) {
let d = distances[cur] === Infinity ? 0 : distances[cur];
d += neighbor.weight;
if (d < distances[neighbor.node] {
distances[neighbor.node] = d;
history[neighbor.node] = cur;
pq.enqueue(neighbor.node, neighbor.weight);
}
}
}

Great! Next, let’s build up our path to return, as well as returning the total distance along that path. Instead of breaking out of the loop, let’s build our result there and return from the function:

if (cur === v2) {
const path = [], distance = distances[cur];
while (cur) {
path.push(cur);
cur = history[cur];
}
return ({ path: path.reverse(), distance });
}

And that’s it! If you were to run this using a as the starting point and e as the end point, your result should look like this : { path: [ ‘a’, ‘c’, ‘d’, ‘f’, ‘e’ ], distance: 6 }

Author’s Note:

The code presented throughout this post is written in JavaScript, using ES6 syntax. For the complete code, please go here.

The observant reader may notice that the graph presented does not conform to the triangle inequality. If this bothers you, just pretend that the weights given are not actual distances, but may be representative of some other metric. ¯\_(ツ)_/¯

The Startup

Medium's largest active publication, followed by +754K people. Follow to join our community.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store