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

shortestpath
dijkstra
algorithm
graphtheory

(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:

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


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

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?


#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.


(Command-Line Ninja) #4

Oh nice! I’ve never heard of that!


(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.


(random-man) #6

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


(random-man) #7

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


(oaktree) #8

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