# Graph Algorithms (Part 1.0): Dijkstra's Shortest Path [Concept]

(oaktree) #1

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

7 Likes

Graph Algorithms (Part 1.1): Dijkstra's Shortest Path [Code v1]
Post Coherency and Adherence to Good English
Routing Protocols ~ OSPF

Man. Really good stuff @oaktree! In this example, could “distance” be exchanged for “speed/ping” for networks? I can picture this being useful for calculating the best route between nodes etc. What are your thoughts?

0 Likes

#3

@pry0cc, there is a routing protocol known as OSPF where “SPF” stands for Shortest Path First. It’s used almost everywhere and the algorithm behind it is Dijkstra’s. Even though its networking implementation is confusing, I highly recommend looking it up so you can understand the high-level image at least. It’s quite interesting.

1 Like

Oh nice! I’ve never heard of that!

0 Likes

(oaktree) #5

What the values of the edges mean is up to the implementer. If you were doing routing, you’d probably care about ping, yes.

0 Likes

(random-man) #6

Nice bro! I love how this is introducing algorithmic concepts to people.

1 Like

(random-man) #7

Also, I think that a lot of graph theory is applied in social media algorithms as well.

1 Like

(oaktree) closed #8

This topic was automatically closed after 30 days. New replies are no longer allowed.

0 Likes