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