Part One: Dijkstra's Algorithm
In computer science, an algorithm is a programmatic method to solve a problem. For an application, robot, or video game character to act intelligently, it must employ algorithms. It’s important to note that merely writing algorithms into one’s software does not make the device that runs that software artificially intelligent. As an example, a piece of software that can take in a list of random, shuffled numbers and sort them would merely use a set of programmed rules and instructions to do so. This is not a display of artificial intelligence. Nevertheless, behaving intelligently requires solving simpler problems of that sort as a foundation.
A staple of introductory algorithms courses is Dijkstra’s Algorithm, which solves the single-source shortest paths problem on a graph.
A graph in this context is a collection of nodes and edges. These nodes and edges can represent any number of things, but for the purpose of this explanation, nodes will represent positions, and edges will represent paths between positions. Undirected simply means that none of these edges are one-way: if there is an edge between two nodes, each can be reached from the other.
The numbers on the paths represent weights, which can be thought of as the number of steps it takes to get from one node to another. Dijkstra’s Algorithm will give you the length of the shortest path from source node A to every other node in the graph. In this case, the solution is:
That’s pretty easy to verify with the human eye, but how did Dijkstra’s Algorithm arrive at these results? Fortunately, although we are very much entrenched in computer science theory, algorithms such as this are easy to talk about without so much as a mention of code. It is, after all, humans who write software, so it follows that the code they write should flow intuitively from their more human understanding of the problem.
First, a look at the generalized algorithm for any case.
You will be keeping up with two lists of nodes (nodes that are visited and nodes that are unvisited) and a table of each node’s shortest known distance from the source node (in this case, A).
1. Consider all nodes unvisited by the algorithm, and consider distances from the source to all other nodes unknown. The distance from the source to itself is 0.
2. Visit the unvisited node with the smallest distance to the source (for the first step, this will be the source, as “unknown” is tantamount to infinity). Then perform the following sub-procedure on the node we’ll call v for “visiting.”
a. If you are visiting a node, that means you have successfully calculated its minimum distance from the source (I empathize with a desire for proofs, but proving the veracity of Dijkstra’s Algorithm is not the aim of this article). So we know the minimum distance from A to v.
b. Using that knowledge, look at all of the unvisited neighbors of v (ones it has an edge to). You can now calculate how far they are from the source by way of v by simply adding the corresponding edge weight to v’s distance. If this calculated distance is shorter than the distance currently known to be the shortest path from the source to v’s neighbor, then update your information to reflect this.
c. Once all neighboring nodes have been considered, v can be added to the visited list. It will never have another operation performed on it again
3. The remainder of the algorithm is simply to continue the steps listed under item 2 until all nodes are visited.
Now, here’s the list of steps for the above example graph.
Visited: [None] – Unvisited: [A, B, C, D, E]
Immediately visit A, since it was predefined as the source. Following the steps under item 2 in the algorithm description, record the distances from A to its neighbors, B and D. They can be trivially found to be 6 and 1 respectively. We can update our table of distances.
Of course, 6 will not remain the shortest path to B, but it is accurately recorded as the shortest path found so far. All of A’s neighbors have been updated, so add it to the visited list.
Visited: [A] – Unvisited: [B, C, D, E]
Proceed to visit the nearest unvisited node, which is now D. Update its neighbors’ distances. To do so, add the distances from D to its neighbors to the distance from D to the source, which is now known to be 1. This gives a distance of 3 for B and 2 for E, which are both shorter than their previous entries. Update the table and add D to the visited list.
Visited: [A, D] – Unvisited: [B, C, E]
E is now the nearest unvisited node, so visit E. Update its neighbors’ distances. C’s distance is found to be 7, so replace its currently unknown distance. B’s distance is found to be 4 by way of E, which isn’t shorter than the shortest that has been found so far, so leave it as 3. Add E to the visited list.
The table now matches the solution provided earlier, but the algorithm will still look at B to see if any nodes can be reachable more quickly by way of B. None can, so B is added to visited. Because C is the last remaining node, it does not have to be looked at. The shortest distance from A to every other node has already been found, and C will have no unvisited neighbors to look at. The algorithm has finished and found the correct answer.
This demonstration of how Dijkstra’s Algorithm finds these paths shows that a computer can take in graph data and indicate the lengths of the shortest paths from one location to every other location. This is a useful set of data, but it is arrived at using an iterable procedure, which I established earlier does not qualify as intelligent behavior. But it’s not far off. In my next piece on artificial intelligence, I’ll take a look at the idea of an intelligent agent and how the concepts of planning and decision-making make the difference between mere problem solving and intelligent behavior. I will also look at the A* (“A-star”) search algorithm as an elementary (yet highly important and widely used) example of informed pathfinding.
Join the conversation! Comment on this article at This Old Neon‘s community forums.