Dijkstra's algorithm in 3 minutes — Review and example

today I'm going to teach you how to run Dijkstra's algorithm on a weighted directed graph Dijkstra's algorithm tells you the shortest distance from one node to every other node in the graph this differs from prims and kruskal's which result in minimum spanning trees let's use the following graph for our example we'll keep a list of unvisited nodes at the bottom our first step is to pick the starting node let's choose a we'll use the table on the right to keep track of distances remember the distances we are measuring are from our starting node a we put 0 for a and infinity for the others as we haven't visited them yet the next step is to examine the edges leaving a we can reach B and C from a so let's update the chart with the corresponding costs next we look at the chart and pick the smallest edge of which the vertex hasn't been chosen in this case C let's cross off see in the unvisited node list marking it as closed after choosing C we examine the edges leaving seat and update the chart accordingly B is now reachable from a with the cost of three by traveling through Z also D and E become reachable for the first time let's do the same thing as before choosing the smallest path with a none closed node this time is B we repeat the process examining the edges leaving B and updating the cost of getting to D and E now we choose D this time there are no updates to our table as there are no edges leaving D finally we choosey again there are no updates but this time because the edge leaving II does not result in a shorter path all the edges in the graph have now been visited and are closed here is the shortest path from a to the other nodes the time complexity of Dyke shows is Big O of e + V log B if a Fibonacci heap is used put simply this is a result of creating the queue of distance values and looping through the edges of each node here is the pseudo code for Dijkstra's algorithm for more information please visit the source shown below in the description and that's it I hope this video gave you a good understanding of Dijkstra's algorithm

Channel: Michael Sambol

Views: 587,106

Rating: 4.8489971 out of 5

Keywords: Dijkstra's Algorithm, Dijkstra's, Dijkstra, Graph Theory (Field Of Study), Graph Search, Software (Industry), Mathematics (Field Of Study), Algorithm, Algorithms, Dijkstras, Dijkstra's Example

Id: _lHSawdgXpI

Length: 2min 45sec (165 seconds)

Published: Mon Sep 15 2014