Description

In this episode, we talk about Dijkstra's algorithm, which can be used to determine the shortest path from one node in a graph to every other node within the same graph data structure, provided that the nodes are reachable from the starting node. It's super important, and you'll see why when you learn about the weighted graph!

Show Notes

This episode of the Basecs podcast is based on Vaidehi's blog post, Finding The Shortest Path, With A Little Help From Dijkstra from her basecs blog series.

Transcript

[00:00:02] SY: Welcome to the Base.cs Podcast where we explore the basics of computer science concepts. I’m your host Saron, Founder of CodeNewbie.

[00:00:09] VJ: And I’m Vaidehi Joshi, Author and Developer.

[00:00:12] SY: And she is the brilliant mind behind the Base.cs Blog Series. Today, we’re talking about.

[00:00:16] VJ: Dijkstra’s algorithm.

[00:00:19] SY: This season of the Base.cs Podcast is brought to you by Educative. Educative has a ton of online coding courses, including how to become a machine-learning engineer and a practical guide to Kubernetes. The comprehensive and interactive text-based courses give you in demand tech skills. And since it’s text-based, there’s no scrubbing back and forth video to find the content you need. So learn better and faster with Educative and get a 20% site-wide discount by going to educative.io/basecs.

[00:00:55] Okay. I don’t know if I’ve ever told you this, but Dijkstra sounds like something you’ll use to hurt me with. Like, this does sound like, “I’m going to cut you with my Dijkstra.” Do you know what I mean? Like, doesn’t it sound like really aggressive?

[00:01:08] VJ: Yeah. It’s like, “I’m armed and dangerous. I brought my Dijkstra on this adventure.”

[00:01:12] SY: Yes. Yes. Yeah. Like, I would want it maybe in a forest but like not to work. You know? I guess it’s too aggressive, but it’s a very popular algorithm. It is super, super popular, also a little intimidating maybe because of how it sounds, but let’s talk about what we use it for. What do we use Dijkstra’s algorithm for?

[00:01:31] VJ: So Dijkstra’s algorithm is what we can use to help determine the shortest path from one node in a graph to pretty much every other node. And that can be really helpful if you’re trying to figure out how to get from one place to another, but not just…

[00:01:49] SY: Like a map?

[00:01:50] VJ: Yeah, exactly, like a map, which I guess graphs are just maps really. The nice thing though is that you don’t just have to find a path through the graph from point A to point B. You’re finding the shortest path through the graph from point A to point B.

[00:02:06] SY: That sounds really useful.

[00:02:07] VJ: It’s pretty cool. It basically is an algorithm that runs until every single vertex in the graph has been visited and what I really like about it is it does some fancy stuff where it’s basically like caching. Basically as it runs through the graph, it keeps like a log or like a little cache of like, “Oh, right now the shortest path to this place is through these set of nodes.” And if you ask it at any point what’s the shortest path from point A to point B, it’ll tell you. And the cool thing is it sort of just updates this cache of which nodes lead to where and which path is the shortest as you run the algorithm. So what’s cool about Dijkstra’s algorithm is that once you run it, you can kind of just use the results of it and you don’t have to run it again unless your graph changes.

[00:03:00] SY: So if we want to run Dijkstra’s algorithm, where do we begin?

[00:03:06] VJ: This is a great question. So. we have to begin at the beginning. Specifically, we need to talk about a specific concept that we haven’t really gone into in this podcast.

[00:03:16] SY: Okay.

[00:03:17] VJ: We’ve talked about different types of graphs, directed, undirected, directed and acyclic and cyclic. But something we haven’t really gone into is weighted graphs and you really need to know what weighted graphs are in order to talk about Dijkstra’s algorithm, because in order to find the shortest path or the most efficient path, you care about the weight of getting from one node to another, and the weight is associated with the edge that connects two nodes.

[00:03:48] SY: Okay. So if I have a very simple graph, A, B, C, a triangle connected to each other, and I’m trying to go from A to B, you’re saying that the edge connecting A to B would have a weight?

[00:04:00] VJ: Yes. And the weight of that edge, it represents like the cost to get between A and B or you can also think of it as like the distance between A and B or the capacity of what can be transported between A and B. And this sort of ties into what you said earlier, which is that graphs are maps. So like if you think about a map where A, B, and C are locations, maybe to get from A to B is a short distance or maybe it’s a far distance. And the way that you could represent that is by adding a weight to the edge that connects Node A and Node B, and that weight could represent the distance between it and you have to care about that because you could have an edge between two nodes, but like what is the weight? You might want to know.

[00:04:46] SY: Yeah. Okay. So it sounds like the way you’re talking about it, it sounds like we want less weight, like the lower the weight, the cheaper it would be to get to a node.

[00:04:54] VJ: Yeah, that’s right. The less the weight, the less the cost, the less than the distance between two nodes. And to tie it back into Dijkstra’s algorithm, if you’re looking for the shortest path between two nodes, you care about choosing the path or choosing an edge to take that has less weight than another one that will get you to the same place. So to that end, the shortest path should theoretically take you down all the edges that will be less in weight than other ones.

[00:05:25] SY: Yeah, cheapest to get to. Okay. So going back to our example, A, B, C, right? Got my three nodes, got my triangle. Let’s say to get from A to B, it costs five. So like a weight of five. A to C is a weight of two. C to B is a weight of one. So if I’m trying to get from A to B, without any of these weights, I would say, “Just use the edge from A to B,” right? What are you going to do? Like go through C to get to the edges. That’s just nonsense.

[00:05:55] VJ: Yes. Right. Just literally just go to A.

[00:05:56] SY: It’s obvious. You just go there.

[00:05:58] VJ: And then go to B.

[00:05:59] SY: Yeah. But with the weights, it ends up being a little bit different.

[00:06:03] VJ: Yeah, you’re right. With the weights, when you’re taking those into consideration, now you sort of have to like stop and think for a second because A to B is sort of like a nonstop edge.

[00:06:16] SY: Yeah, nonstop.

[00:06:17] VJ: You don’t have any layovers.

[00:06:19] SY: Yeah, no layovers.

[00:06:20] VJ: You don’t have to stop anywhere, but like it’s nonstop, but the weight of it is five as you mentioned.

[00:06:26] SY: Yeah, a little pricey.

[00:06:27] VJ: But then that’s direct, but it’s pricey. But if you go from node A to C, that’s a weight of two and then C connects you to B, and that’s a weight of one. So cumulatively, if you took the path of A to C to B, you would take an edge that costs two and then an edge that costs one, which really means the whole path to B would be three. So it seems not as intuitive, right? It feels weird. Like, “Oh, I’m taking the longer path. I’m going roundabout. I’m going from A to C to B instead of just A to B.” But in this case, when you take the weight of all these edges into consideration, A to C to B is actually the shortest path if you’re trying to get from node A to B.

[00:07:13] SY: Okay. So finding the shortest route like we just did seems pretty straightforward, right? Like I compare one edge, I compare the edges of another route, and then I decide one is smaller, like that feels like, you know, like pretty straightforward, not really a big deal. But when I hear about Dijkstra’s algorithm, it sounds like this really big, intimidating thing. So what am I missing?

[00:07:35] VJ: So you’re right to feel like adding up the weights of all the edges is easy. Like, yeah, it was pretty straightforward. Our example graph was just three nodes, but like what if we had a graph with hundreds or even millions of nodes? And I was like, “Saron, find the shortest path.” I don’t know if it would feel so easy. And in that case, I think having an algorithm to sort of simplify it for you and do the legwork of like finding the shortest path, I don’t want to traverse through all the nodes. I just want to find the shortest path. That would be really helpful, I think in that situation. And that’s what Dijkstra’s algorithm does. It helps us find the shortest path between two nodes no matter how big the graph is. You can still apply the algorithm to that structure.

[00:08:23] SY: So let us actually walk through the steps of the algorithm. So first of all, how many steps are we talking about here?

[00:08:31] VJ: So when it comes to the actual steps of the algorithm, it’s pretty straightforward. There’s actually only four steps, and you sort of just repeat them until you’re done running it and effectively until you’re done checking all the vertices in the graph. So these four steps, we’ll go one by one through them. The first one is that every time we set out to visit a new node, we’re going to choose the node with the smallest known distance or cost to visit first, because we’re trying to find the shortest path so it makes sense to visit the node that is the closest to us first.

[00:09:13] SY: Yup.

[00:09:13] VJ: Next, step two, once we’ve moved to the node that we’re going to visit, we’re going to mark it as visited, but also we’re going to check each of its neighboring nodes, and what that means is we’re going to like look at the edges that connect to it and see like, “Okay, here are its neighbors and the edges that connect to each of its neighbors cost a certain amount.” So we’ll make a note of that. Step three is that for each neighboring node, we’re going to calculate the cost to get to that neighboring node based on the edges that we’ve already looked at. So we’re just going to sum up the cost of the edges to get to the neighboring nodes that we haven’t visited, but we know we can visit. And finally, step four is that if we find a way to get to a node using a path or using an edge that is shorter than a known path, we’ll update that shortest distance that we have on file for that vertex.

[00:10:21] SY: Okay. So we have a file.

[00:10:23] VJ: Yeah. It’s sort of like a little cheat sheet. I like to think of it like a cache sort of where for every single vertex we’re going to keep track of two things or I guess really three things. First thing we’re going to keep track of is have we visited it. That’s pretty simple. That’s not new to us. We’ve seen that before.

[00:10:39] SY: Yup.

[00:10:40] VJ: And then we’re going to keep track of the shortest distance to that node from our starting node, which basically means what’s our current status for getting to this node, what’s our shortest current known path. And that’s something that could change as the algorithm goes on and on. And then finally, the third thing we’re going to keep track of is what was the previous vertex that we came to this node from. So we’ll keep track of the shortest distance to a node and the vertex that we took to get there, to get that shortest distance.

[00:11:13] SY: Okay. So if we look at our triangle example, our A, B, C example, we can tell pretty intuitively just by looking at it, there’s only like three edges total. We can tell that from A to B is five, from A to C to B is three. Therefore, A to C to B is actually the shortest path, but I kind of want to walk through it using these four steps just to kind of get a feel for it. Can we do that?

[00:11:37] VJ: Yeah, let’s do that.

[00:11:39] SY: Okay. So A, B, C, if we wanted to run Dijkstra’s algorithm on A, B, C, what’s the first thing that we would do?

[00:11:48] VJ: So the first thing that we want to do is we need to sort of look at our information on file or our cache, so to speak. So I said that we have a couple things we want to keep track of. We want to keep track of what vertices we have. So in this case, we have three, A, B, and C. but for each of those, we want to know, “Have I visited it?” So that’s the first thing. Then we want to know, “What is the shortest distance to this node from our starting node?” And then we want to know, “Where did we come from or the previous for vertex? Like how did we get to the shortest distance?”

[00:12:25] SY: Yeah.

[00:12:26] VJ: So in the case of A, B, and C, we haven’t visited anything and we also don’t know the shortest distance to anything right now. So for that piece of information basically the shortest possible distance to all these nodes is infinity. We don’t have any. It could be anything. The distance could be one. It could be like literally infinity. We just don’t know. It’s not information we have yet.

[00:12:51] SY: Interesting.

[00:12:51] VJ: And similarly, we don’t know what the previous vertex because we haven’t run the algorithm yet.

[00:12:57] SY: Right. They’re anywhere.

[00:12:58] VJ: Yeah, it’s our starting state. We have nothing to do yet. So the first step is we have to pick a starting node. So where do you want to start?

[00:13:07] SY: Well, we’re trying to find the shortest path from A to B. So we would start at A.

[00:13:12] VJ: Great. So the first thing we’ll do is we will go and visit Node A and in our little cache, we can say, “Okay, we’re visiting A,” and so we’re just marking it right now as visited.

[00:13:26] SY: Okay.

[00:13:26] VJ: And the other thing is that because we’re at Node A, we actually have our starting node and we know the shortest distance to our starting node because we’re literally added right now.

[00:13:39] SY: True.

[00:13:39] VJ: And so the shortest distance to A, from A is? Maybe you can help me out.

[00:13:46] SY: Zero.

[00:13:47] VJ: Yeah, it’s zero. And that's kind of the easiest…

[00:13:49] SY: Okay. I was hoping that wasn’t a trick.

[00:13:52] VJ: It takes me back to when we are counting in binary. Now it’s like, “What comes after ten?” And you’re like, “Eleven?” But you are right.

[00:14:01] SY: Once again.

[00:14:02] VJ: Yeah, once again, eight seasons later, here we are. But when we visit Node A, because that’s our starting node, we immediately know one piece of information, which is that the shortest distance to A is zero because you started A, and therefore there is no distance to get there.

[00:14:19] SY: Right.

[00:14:20] VJ: So you also know that you don’t need a previous vertex. So that’s the one piece of information we also don’t care about really because when you start at A, the previous vertex was nowhere. You just started at A. And there’s no distance to get to A, so the distance to get to A is also just zero. So nothing exciting.

[00:14:36] SY: So we’ve basically done nothing. Got it. Cool.

[00:14:39] VJ: Yeah. We visited a node.

[00:14:40] SY: Yeah. Yeah. Yeah. We visited and then we left with nothing.

[00:14:44] VJ: Well, I guess the next step is where things will get interesting. So you’ll remember that when we visit a node, we need to check each of its neighboring nodes. Right?

[00:14:54] SY: Right.

[00:14:55] VJ: And part of that was also figuring out the distance to each of those neighboring nodes. So maybe you can take a stab at that.

[00:15:03] SY: Okay. So I’m at A, I’ve got two neighboring nodes. I have my B and I have my C. So we’re going to look at the cost or the length of getting to each of those. So to go from A to B, it takes five. And then to go from A to C, it takes two.

[00:15:22] VJ: Right. So we have those two pieces of information. We haven’t visited B or C. We’re just kind of looking at…

[00:15:27] SY: We’re looking over. We’re checking them out.

[00:15:28] VJ: Yeah. Yeah. We’re like checking out airline flights and we’re like, “Well, we could go this way, like we can go to Austin or we could to New York. We’re not committing. We’re just looking at this distance.”

[00:15:38] SY: Just looking around. We’re on KAYAK.com.

[00:15:40] VJ: Yeah.

[00:15:40] SY: That’s where we are.

[00:15:42] VJ: The part of the algorithm where we just like browse.

[00:15:44] SY: Yeah. Yes.

[00:15:48] VJ: Okay. So we’ve looked at the two neighboring nodes. We know that it costs five to get to B and two to get to C.

[00:15:55] SY: Right.

[00:15:56] VJ: And if we look at our cache of information, right now the cost of getting to B, the shortest path, is infinity, and the shortest…

[00:16:05] SY: Right, as far as our cache is concerned.

[00:16:07] VJ: Correct. And as far as C goes, it’s also infinity.

[00:16:11] SY: Right, because we haven’t been there. We don’t know what that’s about.

[00:16:14] VJ: Yeah. This is the first time we’re sort of looking at how to even get to these. So amazingly, we found something that is shorter than infinity in both cases.

[00:16:22] SY: Thank God.

[00:16:24] VJ: So to get to Node B from Node A costs five, but five is less than infinity. So we can update our current known path to B.

[00:16:33] SY: Okay.

[00:16:34] VJ: So we’ll go into our cache, this little log of information, and we’ll update the shortest cost, the least cost to get to B is now five instead of infinity and the way to get there is via Node A. So we can also update that.

[00:16:51] SY: Okay. So we are looking over it. We’re like checking it out. We’re browsing C and we know that to get from A to C is two. So for C in my little column that’s checking like the shortest distance, I’m going to cancel out infinity and I’m going to replace it with the number two. And then for my visited from, I’m going to change that from what was empty before. I’m going to update it with Node A.

[00:17:21] VJ: Correct. And basically the situation we’re in now is we’re still visiting Node A, but we’ve kind of taken a peak at two of its neighbors and we’ve looked at two potential paths to get there and the state of our universe based on where we are on KAYAK.com right now, the KAYAK.com part of the algorithm, we know that to get to B, the current known shortest path costs five and that’s via A. And to get to C, the current known shortest path costs two and that’s also via Node A.

[00:17:56] SY: Right.

[00:17:57] VJ: So now what we want to do is we basically want to pick the neighbor to visit that costs the least and that’s where we’ll go next.

[00:18:06] SY: Right. And that’s C because C is two. Okay. So basically saying like, “I checked out these two flights, I’m going to pick flight C.” So now can I move on and like visit flight C?

[00:18:19] VJ: Yeah. Yeah. We can actually move on from A to C.

[00:18:22] SY: You can let go there. Yeah. Okay. So now that we are on flight C, we’re on like the page of flight C, we can mark it off as visited because we’re visiting it, right? That’s the first thing. And then we’re going to ask C, “Okay, who are your neighboring nodes?” And C is connected to A, we’ve already been to A so we’re not going to go back to A. But C is also connected to B, which we have not visited yet.

[00:18:48] VJ: Yup.

[00:18:48] SY: I’m going to say, “All right, what is the cost of getting from C to B?” And the cost is one. But we don’t actually care about getting from C to B. We care about getting from A to B, right? Because we’re always anchoring ourselves from the very first vertex that we’re working with. Is that right?

[00:19:07] VJ: Yeah. And actually it’s because the way to get to C right now is through A, right, and you’re standing at Node C and you want to go to B from C, so really what you’re saying is I’m going from A to C to B. That’s the real path we’re taking. So it’s not just from C to B. We have to get to C somehow. So it’s really the cost of A to C plus the cost of C to B.

[00:19:35] SY: Okay. So C to B is one, but to get to C in the first place from A is two. So I know that my total cost to get to B is actually three.

[00:19:45] VJ: Yes. And what’s interesting is now if we look at our cache, our current knowledge, our shortest path to B currently we think is five and that’s through Node A. The previous vertex was Node A in that path.

[00:20:04] SY: Yep.

[00:20:04] VJ: But now you’ve discovered that there is a path to B that is less than five.

[00:20:11] SY: Yes, I did. It does right. Okay. And that path is, or that length is three. So if I remember the steps correctly, I think that means I can go back to… on my cheat sheet, I can go back to Node B and where it used to say five. I can update that and I can now say three.

[00:20:35] VJ: And when you do that, you also want to update the previous vertex that gets you to Node B. And in this case, if you want to get to Node B and for it to cost three, you have to take the path of A to C to B. So you basically updated two things in your little cache cheat sheet thing. You’ve said, “Okay, B no longer costs five.” Via Node A, we actually have discovered it costs three via Node C.

[00:21:06] SY: So now that I’ve done that, I guess there’s only one node we haven’t visited, that we’ve talked about B, but we’ve never actually visited B. So do I have to go to B now?

[00:21:17] VJ: So yeah. We’re at Node C, that was the last thing we visited, and the steps are looking at its neighbors, find the one with the least cost and go visit it. In this case, C really has only one neighbor that we can visit here, which is B, and conveniently, it only costs one and there’s really nothing else to compare it to. So we have to visit B next.

[00:21:39] SY: Okay. So now I’m at B, I’m looking at my cache. I can now mark it as visited because I’m visiting it and then I’m asking, “Okay, B, do you have any neighboring nodes?” At least ones that we haven’t visited, right? Because technically, it does have an A and a C. We’ve already been to A and C. So there’s nothing left to do, I don’t think.

[00:22:03] VJ: Yeah. We’re basically at the end because we visited all the nodes. We have the shortest path to every node and the way to get there and we figured out a couple of things. First, we’ve answered your question of what’s the quickest way to get from A to B. Right? And it turns out, if we look at our cache, the quickest way to get from A to B is through Node C and it’ll cost us three. We’ve also figured out the quickest way to get to Node C, and that’s from Node A, and it costs two.

[00:22:32] SY: Yeah, and it cost us two. Yeah.

[00:22:34] VJ: Yeah. So really what we did is we figured out the shortest path from Node A to all the other nodes in the graph, which there’s only three nodes. And we looked at this like… we can kind of like imagine this graph and be like, “Oh, yeah, it’s obvious,” but this is what it looks like when we ran Dijkstra’s algorithm on this tiny little graph.

[00:22:58] SY: Okay. Okay. I feel good about that. I feel totally good about that. I like that it made sense intuitively because like you said, it’s a pretty small graph. We can just go look at it, but then we like backed it up with some computer science.

[00:23:11] VJ: With some real computer science.

[00:23:13] SY: With some real CS. Nice. Okay. Cool. But that is a really simple example. I imagine things get a little funkier when it gets bigger.

[00:23:22] VJ: Oh, yeah. We could go from three nodes to five and it could become so much more complicated.

[00:23:30] SY: Oh, goodie! Okay. Cool.

[00:23:33] VJ: So if you did the same algorithm with five nodes, actually I think we should do that. Maybe next episode we’ll do Dijkstra’s algorithm like the real deal on a larger graph and that’s when we won’t be able to as easily guess what the shortest path is and then we’ll really need Dijkstra to help us out.

[00:23:56] SY: Okay. I’m down for that.

[00:23:58] VJ: All right.

[00:23:59] SY: And that’s the end of today’s show. If you liked what you heard, please leave us a review and make sure to check out Vaidehi’s blog post. Link to that is in your show notes. I also want to give a huge shout-out to Educative, the text-based online coding course platform. My producer and I got a chance to give it a try. I took “become a front-end engineer”. And Levi, what did you take?

[00:24:20] LS: I took “Learn Python from scratch”.

[00:24:23] SY: And what do you think?

[00:24:24] LS: I thought it was really great. So I’ve been learning Python a little bit and this sort of like…

[00:24:30] SY: Because I’m making you.

[00:24:31] LS: Because you’re making me. True. You’re not making me learn Python specifically.

[00:24:34] SY: That’s true.

[00:24:35] LS: But it is what I chose. So I was a little bit familiar, but I found that these courses, they’re laid out in a really intuitive way, there’s like the sections that lead seamlessly one into the other, the Python 1 goes from data types and variables to conditional statements, functions, loops, and then each section has a quiz to make sure that you’re not just blasting through and like the information is going one way and not the other.

[00:25:04] SY: I love the quizzes.

[00:25:05] LS: Yeah. It really called me out on my BS.

[00:25:07] SY: Yes.

[00:25:09] LS: I was like, “Yeah, yeah, I get it. I get it. I get it.” And then I took the quiz and they’re like, “You don’t get it.” And I was like, “Aha!”

[00:25:15] SY: You got me.

[00:25:16] LS: You got me. And then throughout all of these different sorts of sections, you can code within the service itself. So you don’t need like an external coding thing. I should know what that’s called. Do you know what that’s called?

[00:25:32] SY: I’m not going to tell you. I’m not going to give you an IDE.

[00:25:33] LS: No. Yes. That’s what it says, an IDE. Did you know I’m a producer for a coding podcast?

[00:25:40] SY: A technical podcast.

[00:25:42] LS: Yeah.

[00:25:42] SY: Two actually, two technical podcasts.

[00:25:44] LS: That’s true.

[00:25:45] SY: So if you are interested in learning how to code, make sure to check out Educative and you can actually get 20% off by going to educative.io/basecs. That’s B-A-S-E-C-S. Check it out. This episode was edited and mixed by Levi Sharpe.

[00:26:02] VJ: Bye everyone.

[00:26:03] SY: Thanks for listening. See you next week.