# Dijkstra’s Algorithm in Kotlin

Dijkstra’s algorithm answers the question:

What is the shortest path from a start vertex to every other vertex in the graph?

This is useful—we need to do things like route messages through a phone network, and find the best route from point A to point B.

It hinges on the observation that any subpath of a shortest path must also be a shortest path (I encourage you to think about why). Here is my favorite explanation of it, and here is a useful visualization.

My code is more focused on education, mirroring the way I learned it originally at GT. To speed it up, you can make the operation of getting the next vertex to explore (`v`

, in the code) done with a min heap.

Some other good implementations to compare with are Rosetta code, and the one in Kotlin Algorithm Club (what an awesome project!).

So, first let’s write a Graph class, so the algorithm has something to act upon.

Without going too much into the details of initialization and providing a simple API, this is essentially my Graph class (on Github I add an additional constructor).

Now, let’s actually take a look at the algorithm.

Man, Kotlin has fantastic API’s for functional programming.

Here’s the test:

If you’d like to run the code, clone the git repo and get started using gradle.

Wow! You read the whole thing. People who make it this far sometimes
want to receive emails when I post something new.

I also have an RSS feed.