The Introduction To Artificial Intelligence Algorithms #5 - Dijkstra

And what better way to start a series on search algorithms than with algorithms that find the shortest path?

Finding the shortest path - Dijkstra

Dijkstra is the simplest algorithm for finding the shortest path through a graph. It probably won't surprise us that the simplest algorithm is not necessarily the best. So let's try to think how to find the shortest path in such a graph (from point A to point G):

‍

Of course, we take into account that the numbers on the edges mean the length (difficulty) of the path. We can determine the path immediately by sight, but how does the computer find this path? Dijkstra works simply by evaluating the path that is the shortest at a given moment. That is, if we are currently at point A, the shortest continuation of the journey is to visit point B. Length A-B = 3 < length A-C = 5.

We can therefore express the first step of the algorithm with the following animation:

The first iteration of Dijskry (dark blue indicates already equipped points, green and pale blue points in the priority list)

If we would like to continue this way with a second iteration, the shortest path known so far has a length of 3, so we will continue with point B and the second iteration will look like this:

We would then choose point C or E (since their length is the same) and continue in a similar vein. You can find the entire presentation on finding the shortest path here.

Implementation

So let's create a sorted list of vertices (sorted by path length). Each entry in this list will represent a vertex, the length of the shortest known path to that vertex, and the shape of that path. The length of the shortest path is preset to ∞, because we have not calculated any path yet:

data class Item(
    val id: String,
    var length: Int = ∞,
    var bestPath: List = emptyList()
)

But let's not forget that the shortest path from point A to point A has a length of 0. So this point will be on the first place in our priority list. So our priority list might look like this:

val queue = mutableListOf(
    Item("A", 0),
    Item("B", ∞),
    Item("C", ∞),
    Item("D", ∞),
    Item("E", ∞),
    Item("F", ∞),
    Item("G", ∞)
)

And the procedure will be as follows:

1. we select an item from the priority list (the item with the shortest path)

queue.sortBy { it.length }
val item = queue.removeAt(0)

2. we select all edges from the graph connected to this vertex

val edges = graph[item.id]

3. For each of these edges:

a. we calculate the new length from our item to the new point:

val alt = edge.length + item.length

b. If this length is less than found so far, we update the items in the priority list:

val neighbor = queue.first { it.id == edge.id }
if (neighbor.length > alt) {
    neighbor.length = alt
    neighbor.bestPath = item.bestPath + edge.id
}

4. We will repeat the cycle until our target point is at the top of our priority list. That way we will be sure that we know the shortest path to the destination with certainty.

You can find the entire Kotlin implementation on this Gist.

Implementation details

Of course, this algorithm will be slightly different if, for example, we want to get all triplets start-destination-shortest_path, or if we only need to find out the length of the path (we are not interested in the route). However, these and other modifications of Dijkstra are only implementation details and their solution is up to you 🙂

A classic problem/example of this algorithm is traveling through a grid (labyrinth). How about trying to solve a specific problem? For example, check out this task on the Codingame platform.

Problems

The main problem with this algorithm is clear. We do not take into account the existence of the target point in any way. That is, if we see a map of Slovakia and want to get from Banská Bystrica to Košice, our eyes tend to follow the roads heading east from Bystrica, as if they should be looking at Nitra or Bratislava.

We will show how to direct the algorithm's view towards the goal with algorithm A*

Materials

Here I present excellent materials on the issue of Dijkstra's Algorithm:

The best explanation of this algorithm can be found in a video from Computerphile. (With a small flaw and the fact that it ends the cycle prematurely - see point 4. of our algorithm)

The pseudocode on Wikipedia is sufficient.

And lectures from MIT are also a popular source.

Other parts of the series on artificial intelligence algorithms:

• HillClimbing
• TabuSearch
• Simulated annealing
• Genetic algorithms