Artificial Intelligence: Graphs, Dijkstra and A*

A graph is a collection of nodes (also called vertices) with edges between some of them. Each node has a name. An edge can have a label, which is a number.

A graph can represent many different situations. A common one is that the nodes are places and the edge labels are the distances between them. An edge is only drawn when you can travel directly between that pair of places. A graph like this can be used, for example, to find the shortest route between two nodes that are not next to each other.

We could use our own intelligence to find the shortest route from node A to node D: list every possible route and add up the distance of each one.

For a graph with 100 nodes, this would take far too long. Luckily, a number of artificial intelligence algorithms have been developed to solve this kind of problem.

Graphs are useful in AI because they give a structure to relationships between things, and many AI problems can be turned into finding a path through a graph.

Dijkstra’s algorithm finds shortest paths in a graph. For example, it can be used to work out the shortest distance between two towns.

Take the problem of finding the shortest distance from Town A to Town E. On a small graph like this, we could simply use trial and error:

The table shows every possible route that does not go round a circuit. The shortest path is A to C to D and then to E, a distance of 80.

As a quick reminder, graphs are made of vertices (or nodes) and edges, which are the connections between them. Some vertices are not connected, so there is no edge between them. A weighted graph, like the one above, has a value (a weight) on each edge.

Dijkstra’s algorithm works out the shortest path from a single source (the starting vertex) to every other vertex. So it also gives the shortest path from the starting vertex to any one destination vertex, as in the example above. It only works on weighted graphs with positive values on the edges.

Many common applications need a shortest path algorithm, and Dijkstra’s algorithm is likely to be the basis of all of these:

• Geographic information systems (GIS), such as satellite navigation systems and mapping software. The vertices are geographical locations and the edges show the distance or the drive time.
• Telephone and computer network planning. The vertices are the devices on the network, and the edges could be the physical distance or a measure of what the network can carry, such as bandwidth.
• Network routing and packet switching. The vertices are network devices and the edges are the connections between them. The algorithm can be used to send data packets along the most efficient route. In fact, there is a routing protocol for TCP/IP networks called OSPF, which stands for open shortest path first.
• Logistics and scheduling. Wherever there is a large network of vehicles, such as delivery vans, buses or aeroplanes, the algorithm can be used to calculate the best routes.

Here is how the algorithm works on the graph in the next section, where we want the shortest path from vertex A to vertex G (rather than from A to every vertex).

1. Start from the first vertex, in this case A.
2. Work out the weight (also called the cost) of each edge between that vertex and the vertices it is joined to. For example, A to B is 2 and A to C is 5.
3. Move on to the next nearest vertex and repeat. Here it is B. This time you add the weights together to get a total weight from the start. For example, A to B to C is 2 + 4 = 6, and A to B to F is 2 + 7 = 9.
4. There are now two ways to get from A to C: direct, with a weight of 5, or A to B to C, with a weight of 6.
5. As we want the shortest path, we now know the best route from A to C is direct. Keep this and ignore any longer routes.
6. Repeat until every vertex has been visited and you reach the destination vertex, in this case G.

The working gets more complicated because you must keep a running total of the weights along each route, and then choose the shortest. The table traces each stage of the algorithm. Each entry shows the shortest total distance from A found so far, with the vertex it came from in brackets. Bold entries are final: that vertex has been visited and will not change.

Note D and E are not finished in this table, because we only wanted the path to G. A full run of Dijkstra’s algorithm, which finds the shortest path to every vertex, carries on: D stays at 11 (A, C, D) and E becomes 14 (A, C, D, E). E is not really unreachable.

You can check the answer by working out the total weight of every other route from A to G that does not go round a circuit. All of them are longer than 11:

The A* search algorithm builds on the ideas of Dijkstra’s shortest path algorithm to find the shortest path between two nodes faster. It does this by adding a heuristic, which helps it decide which node to look at next as it moves along the path.

Dijkstra’s algorithm finds the shortest path from the start node to every other node. As well as being faster, the A* algorithm is different because it only looks for the shortest path from the start node to one target node.

Heuristics, sometimes called heuristic functions, give “good enough” answers to very complex problems where finding a perfect answer would take too much time. In A*, the heuristic makes the search faster, and as long as it never overestimates the distance left, A* still finds the shortest path.

One drawback of Dijkstra’s algorithm is that it can, and will, evaluate paths that will never give the shortest route. Imagine finding the shortest route on a map from Karachi to Lahore. Anyone who knows Pakistan’s geography would not bother to look at a route through Quetta.

The trade-off between speed and accuracy matters. In some applications, accuracy is less important than computing time. For example, in a SatNav app, a route that is worked out in seconds and is “short enough” is better than waiting 10 minutes for the perfect route.

The A* algorithm uses a heuristic function to help decide which path to follow next. The heuristic function gives an estimate of the lowest cost from a given node to the target node. The algorithm adds the actual cost from the start node, called g(n), to the estimated cost to the target node, called h(n), and uses the result to choose the next node to evaluate. The step-by-step method below shows this in detail.

There is no single best heuristic for path finding, because every application is different. For example, if the cost is a distance, it could be estimated by working out the “straight line” distance between the nodes, perhaps using one of these methods:

• Euclidean distance
• Manhattan distance

But remember that the weights on a graph do not always represent distance.

In this example, you use the A* algorithm on a small graph to find the shortest path from A to F. If you have not studied Dijkstra’s shortest path algorithm yet, start there, because much of the terminology is explained in that topic.

The heuristic function used here is a black box. This means you do not see how it works: the detail is abstracted away, so there is one less thing to think about. The function returns the estimated distance from each node to the target node, F:

On the graph, each heuristic value (in orange) is written next to its node, so all the information you need for the method is in one place.

g-score and f-score. In Dijkstra’s algorithm, you kept track of the cost of each path as you evaluated all the possible routes. Every time a shorter path was found, you updated the cost and the previous node.

In A*, the cost of the route from the start node is worked out, stored and updated in the same way, but it is called the g-score. There is also an f-score: the cost of the path so far plus the heuristic’s estimate of the cost to reach the target node. It is the f-score, not the g-score, that is used to choose the next current node.

Step 1: set up the lists. Start by setting the g-score of every node to infinity (or a very large number), to show that it has not been worked out yet. The f-score can also be set to infinity.

• Make the unvisited list with four headings: node, g-score (cost from start), f-score (cost from start + heuristic) and previous.
• In the node column, list every node, starting with the start node (A in this example).
• Set the g-score of the start node, A, to 0 and its f-score to 10, the value the heuristic function returns for A.
• For every other node, set the g-score and f-score to infinity and the previous node to none.

Unvisited list after step 1:

Now make the visited list with the same four headings. It is empty to begin with and is filled in as the algorithm goes on.

Step 2: A is the current node.

• Pick the node with the lowest f-score in the unvisited list. A has the lowest (10); every other node is infinity. A becomes the current node.
• Look at the nodes that can be reached directly from A (A’s neighbours) that have not been visited yet.
• The edge A to B has a weight of 10. B’s g-score is infinity, and 10 is less, so write 10 and record the previous node as A. h(B) is 15, so B’s f-score is 10 + 15 = 25.
• The edge A to C has a weight of 12. 12 is less than infinity, so write 12 and record the previous node as A. h(C) is 5, so C’s f-score is 12 + 5 = 17.
• The edge A to D has a weight of 5. 5 is less than infinity, so write 5 and record the previous node as A. h(D) is 5, so D’s f-score is 5 + 5 = 10.
• All of A’s neighbours have been looked at. Remove A from the unvisited list and add it to the visited list with its g-score (0), f-score (10) and previous node (none).

Unvisited list after step 2 (the old value is shown after “was”):

Visited list after step 2:

This carries on the A* trace from the previous section, on the same graph, from A to F.

Step 3: D is the current node.

• Pick the node with the lowest f-score in the unvisited list: D (10). D becomes the current node.
• Look at D’s neighbours that have not been visited. You never go back to a node that is already on the visited list.
• The edge D to C has a weight of 6. D’s g-score is 5, so the cost of reaching C through D is 5 + 6 = 11. This is lower than C’s current g-score (12), so update C: g-score 11, previous node D. h(C) is 5, so C’s new f-score is 11 + 5 = 16.
• The edge D to F has a weight of 14. The cost of reaching F through D is 5 + 14 = 19. F’s g-score is infinity, so write 19 and record the previous node as D. h(F) is 0, so F’s f-score is 19 + 0 = 19.
• All of D’s neighbours have been looked at. Remove D from the unvisited list and add it to the visited list with its g-score (5), f-score (10) and previous node (A).

Note By following this method, the unvisited list always holds the lowest g-score and f-score found so far for each node, which is what leads you to the shortest path.

Unvisited list after step 3:

Visited list after step 3:

Step 4: C is the current node.

• Pick the node with the lowest f-score in the unvisited list: C (16). C becomes the current node.
• Look at C’s neighbours that have not been visited.
• The edge C to E has a weight of 11. C’s g-score is 11, so the cost of reaching E through C is 11 + 11 = 22. This is less than infinity, so write 22 and record the previous node as C. h(E) is 10, so E’s f-score is 22 + 10 = 32.
• The edge C to F has a weight of 8. The cost of reaching F through C is 11 + 8 = 19. F’s g-score is already 19, and 19 is not less than 19, so nothing changes.
• All of C’s neighbours have been looked at. Remove C from the unvisited list and add it to the visited list with its g-score (11), f-score (16) and previous node (D).

Unvisited list after step 4:

Visited list after step 4:

Step 5: F is the current node.

• Pick the node with the lowest f-score in the unvisited list: F (19). F becomes the current node.
• F is the target node, so the search is complete. Remove F from the unvisited list and add it to the visited list with its g-score (19), f-score (19) and previous node (D).
• The g-score of F is the cost of the shortest path from A to F: 19.

Final visited list:

Finding the shortest path between two nodes.

The visited list holds data for every node that was examined. Notice that, unlike Dijkstra’s algorithm, the A* algorithm does not necessarily give information for every node in the graph, because the heuristic function steers the search towards the target node. In the example, B and E were never visited.

To find the route of the shortest path from A to F, work backwards through the previous nodes:

• Start at F: its previous node is D.
• From D, the previous node is A.

So the shortest path from A to F is A → D → F, with a cost of 19.

Note The route A → D → C → F also costs 5 + 6 + 8 = 19. A* keeps A → D → F because, in step 4, the new cost to F (19) was not less than the one already stored (19). Either route has the shortest cost.