Graphs in CS

Many problems in real life can be converted into graphs which we can use computers to solve. Graph traversal algorithms are behind your daily commute, online shopping and the food on supermarket shelves. Let's look at some of the basic algorithms used in this field.

Minimum Spanning Tree

Suppose we are Tesco and we want to design our store supply network. Every store needs to be connected to every other store, and we want to have a minimum of route length to save money on fuel. Add stores to the demo, drag them around, and watch it calculate the shortest network.


This works using Prim's Algorithm, which is as follows:

  1. Add a random node to the tree
  2. Find the shortest edge from any node in the tree to any node not in the tree
  3. Add this edge to the tree
  4. Do steps 2 and 3 until every node is in the tree

Dijkstra's Algorithm

It is now Halloween, and Sainsbury's need to deliver their pumpkins cheaply. They already have a supply network, but how do they route the pumpkins to get to each store in the shortest amount of time possible? Add stores and connections (use node numbers, and 0 for the farm), and then click on a store to see the quickest way to route a pumpkin from the farm to the store.


Dijkstra's Algorithm:

  1. Make a set of all the unvisited nodes
  2. Assign every node a distance from the start. For the start it is zero, and for all others it is infinity (because we haven't worked any out yet).
  3. From the unvisited set, we pick the current node to be the one with the shortest distance to the start.
  4. For every neighbor of the current node, calculate the distance from the start to the neighbor through the current node (this is the distance from the start of the current node plus the length of the edge).
  5. If this is less than the distance stored in that neighbor, replace it and add a record to that neighbor that the quickest way is via the current node.
  6. Remove the current node from the unvisited set
  7. Repeat steps 3-6 until the target node is the current node

A# and Black Magic

This algorithm always generates the quickest route, but it's very slow, as it will check any paths up to the length of the shortest path, even if those paths are in the complete wrong direction

However, we can get an estimate of how much further it will be from a given point, and use it to speed up the algorithm. Adding this means it is now called A# (A sharp).

Picking a good estimating function (heuristic) is tricky and generally a case of CS Black Magic. There is also a tradeoff, as a very accurate heuristic will probably take a while to calculate, which might make the whole algorithm slower than a cheaper heuristic.

For the above problem a good heuristic would probably be the straightline distance multiplied by 1.5

To turn a basic Djikstra's into A# we need to store an extra value in each node, which is how long our heuristic thinks it will take to get to the target

Then, instead of picking the next closed node as the unvisited one closest to the start, we pick the one with the lowest (distance to the start + estimated distance to the target). This means the algorithm is now more likely to visit nodes closer to the goal, which is good.


More Stuff

Digital maps need to be even faster than a good A# algorithm, so they use other ideas. Here are some: