Hey 0x00sec! I’ll be taking a pause from my Data Structures series to introduce this community to Graph Theory with Dijkstra’s Algorithm. I only just barely understand this, so bare with me.
Graph Theory (Brief)
There are two main types of graphs:
- Directed Graphs are graphs whose edges go a certain way. For example, the edge from node 1 to node 2 may be different in value than the edge from node 2 to node 1.
-
Undirected Graphs are graphs whose edges’ direction does not matter:
1 -> 2 == 2 -> 1.
This series (the beginning, at least) will focus on undirected graphs.
There can also be cyclical edges, which are edges that point from one node back to that node.
Description of Dijkstra’s
Dijkstra’s Algorithm was created in the 1950s by a man named Edsger W. Dijkstra. Its purpose is determining the shortest path between two points, or nodes, in a graph of points connected by edges.
It has a Time Complexity of O( num_edges + num_nodes * log(2,num_nodes) ). You can see that the number of nodes has a more drastic effect than the number of edges.
Let’s say we have some graph:
Taken from here, a great Intro to Graph Theory that you should totally go read after finishing this.
We want to find the distance between A and H. A is connected to two nodes, B and C. Let’s list out the distance from A to every other node:
- A: 0
- B: 7
- C: 8
- D: ?
- E: ?
- F: ?
- G: ?
- H: ?
But why did I put all the question marks? It’s because, looking from A, we only directly have access to B and C. All other nodes can only be accessed by going through B or C (or a node may be totally inaccessible).
But we’re trying to get to H, right? So, if we start from A, should we move to B or C? Well, which one is closer to A, meaning which edge-length is smaller? Okay, let’s pick B. From B, let’s update our data:
- A: 0
- B: 7
- C: 8
- D: ?
- E: ?
- F: 9
- G: ?
- H: ?
Great. From B we can only go directly to F. Thus, we’ve discovered a distance from A to F. The distance from A to F is determined by the sum of the distance from A to B and B to F, 9. Now, let’s move to F and update our information again:
- A: 0
- B: 7
- C: 8
- D: ?
- E: ?
- F: 9
- G: ?
- H: 12
Oh, would you look at that!? We’re at H now! So we know that the distance from A to H is twelve and our path was A -> B -> F -> H.
Conclusion
That’s it for the concept of Dijkstra’s Algorithm. In Part 1.1, I’ll walk you through the coding of Dijkstra’s algorithm. We’ll be using matrices (2D arrays). I should also tell you now that I’m going to use C++. Surprised? I didn’t think so!
I’ll tell you that it personally took me quite a lot of time to get a grasp on Graph Theory and this algorithm. This article was probably the most helpful thing I found on the internet about Dijkstra’s Algorithm. You should totally go read it. I will be using code I wrote myself in the next tutorial, but it is influenced at least slightly by the author of that article.
Auf Wiedersehen,
oaktree