How Dijkstra's Algorithm Works

to understand what dykstra's algorithm is and how it works let's start with a scenario let's imagine that we have a variety of different towns scattered in different locations some of those towns are connected to other towns with roads such that we could travel along a road to go from one town to another not all roads have the same travel time though one road might take three minutes to travel through while another might take four and our question is this what's the fastest way to get from town a to town b this is a specific example of a more general problem in graph theory where we have vertices in this case our towns that are connected by edges in this case our roads together the vertices and edges form a graph and in particular this graph is a weighted graph because each edge has some value or weight to indicate how costly it is to travel along that edge measured in either distance or time and with this graph we'd like to determine the shortest path from one vertex to another so how does dijkstra's algorithm allow us to do this ultimately we need to figure out how many minutes it will take to get to town b in doing so though it might be useful to figure out how many minutes it would take to get to the other towns too so ideally we'd want to label each town with a number representing the shortest time required to get there but of course we don't know that information yet so instead we'll label each town with the shortest time we've found so far to get to that town before we've started the algorithm we don't have any known way of getting to the towns so we'll label them all with infinity the only town that we can label correctly is our source town a which we can easily label we're starting there so it takes zero minutes to get to this town once we've found the shortest path to a town let's call that town explored for all other towns we'll consider them unexplored we don't yet know what the shortest path to them is so what can we do next dijkstra's algorithm repeats a two-step process first we update our estimates and second we choose the next vertex to explore so let's start with the first step updating our estimates we know we can get to town a in zero minutes and because we can get from town a to town c in three minutes we know we can get to town c in three minutes that's much better than our current estimate of infinity so we'll update our estimate to be three and we can do something similar for town f we can get there in two minutes so we'll update our estimate after we've considered all possible roads connected to town a we're done with this step and now the next step is choosing which town to explore next and the rule is quite simple the town we explore will always be the unexplored town with the smallest estimate in other words the next town we explore should be among all of the unexplored towns the one we know we can get to the quickest in this case that's town f which we can get to in two minutes and now the two-part process of dijkstra's algorithm repeats we first update our estimates by looking at the towns connected to town f it takes five minutes to get from town f to town g so if we can get two town f in two minutes then we can get to town g in seven minutes the sum of those two values likewise we can get to town b in eight minutes and we can get to town e in five minutes we can also get to town c in four minutes two minutes to go from a to f and then another two to go from f to c but four minutes is actually more than our current best estimate for town c which is three minutes so we don't want to update anything here remember for each town we want to store our best estimate for the shortest amount of time required to get there so let's keep going the second part of dijkstra's algorithm tells us to explore the unexplored town with the smallest value and in this case that's town c which we can get to in just three minutes and the process repeats again going through town c we can get to town d in seven minutes and we can also get to town e in four minutes three minutes to town c plus one minute from c to e that four minute estimate is better than our current estimate of five minutes so we'll update our estimate for town e from five to four the next town to explore is town e among all the unexplored towns it has the smallest value notice that each time we explore a new town it's guaranteed that we will have found the shortest path to get to that town since if there were some shorter path we would have explored that shorter path first because we prioritize exploring these smaller values and through town e we can get to town b in just six minutes four minutes to town e plus two minutes to go from e to b so we update our estimate for town b to be six which is better than the previous estimate of eight and now the next town to visit is town b our destination and that tells us that the shortest time needed to get from town a to town b is therefore six minutes and that's dijkstra's algorithm for finding the shortest path in a graph now there are a few things worth pointing out here the first is that technically our algorithm has only given us how long it will take to get from town a to town b and hasn't actually given us which path to follow in order to actually reconstruct that path we'll need to add a step to our algorithm every time we update our estimate for a town we should also keep track of what previous town we visited in order to get to this new estimate if we keep track of that for each of the towns as we progress through the algorithm then at the end we can figure out what the best path is just by following those arrows backwards to the beginning also it's worth noting that this algorithm only works correctly if the weights of all of the edges are non-negative since otherwise some negative length path might result in a shortest path that our algorithm wouldn't be able to find another thing worth thinking about is how we efficiently determine which unexplored town to visit next we want to always pick the unexplored town with the current smallest estimate so some kind of priority queue that gives us efficient access to the next town to visit can make our algorithm faster and that's dijkstra's algorithm for finding the shortest path in a graph we keep track of a distance and a previous town for each vertex the distance for all vertices starts at infinity except for the source which starts at zero and then as long as we haven't explored the destination yet we pick the unexplored vertex with the smallest distance to explore next we consider all edges connected to that vertex and if we can come up with a shorter path to a neighboring vertex then we'll update our distance estimate and remember which town we came from once we've explored the destination we have our answer we'll know how quickly we can get to the destination as well as what the shortest path actually is

Channel: Spanning Tree

Views: 17,146

Rating: 4.976048 out of 5

Keywords: algorithms, computer science, data structures, priority queue, dijkstra, shortest path, graph theory, efficient, network, source, destination, weighted graph, undirected graph, directed graph, binary heap, bfs, breadth first search

Id: EFg3u_E6eHU

Length: 8min 31sec (511 seconds)

Published: Sat Aug 15 2020