YouTube Instagram TikTok How it works FAQ

The fastest way to turn talking videos into clean, searchable text. Free, private and no account required.

About

Built by Rishav Raj with one goal: free transcripts for everyone.

rishav@yttotranscript.com

Transcribe

YouTube to text
YouTube with timestamps
Instagram Reels
TikTok videos

Learn

How it works
FAQ
YouTube transcripts guide

More

Chrome extension
Contact
Privacy policy
Terms of service

© 2026 YTtoTranscript. Made for creators & researchers.

Not affiliated with YouTube, Instagram or TikTok. Respect creators’ copyright.

Lec 17 Dijkstra Algorithm P2 — Transcript · YTtoTranscript

Home/Transcripts/YouTube

YouTube Transcript

Lec 17 Dijkstra Algorithm P2

NPTEL - Indian Institute of Science, Bengaluru · 3,501 words · 18 min read · EN

Watch on YouTube

Share X LinkedIn WhatsApp

Below is the complete, readable transcript of Lec 17 Dijkstra Algorithm P2 by NPTEL - Indian Institute of Science, Bengaluru on YouTube. Read the full text, copy any part you need, or generate a transcript for any video with our free tool.

namaskara we continue our discussions on dxas algorithm in Dyas algorithm we solve the single Source shortest path Problem by determining um the shortest uh path weight um in incremental order okay so we will do n minus one iterations and find the shortest path weights of n minus one vertices in each iteration we

find uh one vertex for which the shortest path distance the shortest path weight is determined uh so we will maintain two sets yes and another set V minus yes so s is the set of all vertices for which Delta value uh are known this is not Delta value or not known so we will

work with the vertices in v v minus s identify a Vertex for which the Delta is known then move that to so determine uh vertex V in V minus s such that Delta V is known or Delta V is computed since for V Delta V is known we have to move V to

yes okay this is what we repeatedly do so how do we uh determine the vertex in V minus s we keep for every vertex in for every V belonging to V minus s we maintain two pieces of information the first one is D of V which is the weight of shortest special path what we mean by special path is a

path from s to V with all vertices other than we are in yes okay so if this is yes there may be several vertices and then this is V this is a special path okay so the special path ends with a Crossing Edge Crossing Edge is an edge going from s to V minus uh yes and this is previous of V

this is the last Edge so we always say the last Edge in the form of the vertex and its previous vertex so p V = to U where u v is the lastage of uh the shortest special path so these two pieces of information we maintain use this to determine the V so how do we determine V we have seen in

Transcribe another video

Paste any YouTube, Instagram or TikTok link to get a free transcript.

Free · No sign-up · Unlimited

Add to Chrome — transcribe in one click

the previous session that if V is a vertex in V minus s such that DV is less than or equal to duu for All U belonging to V minus yes that is V is a vertex with minimum D value V is a vertex with minimum D value every vertex has got a D value

associated with it the value associated with these minimum among all the vertices in V minus s okay in this case we have shown that uh let we then DV is in fact Delta V that means this implies V Delta V is known for V which implies we move V to S now what is to be uh done

look at the definition of the special path definition of a special path is that it's a path which is going through only the vertices of s and then reach now s has become larger we have one more vertex added to S therefore D values are to be updated okay since s has been updated to s Union V

you have mov we need to update du values for U in V minus yes okay the following observation is helpful in identifying for what vertices we have to do the updating and how we do the updating okay so it's a very common sense and simple observation once this is done uh we are done with the details

of uh the algorithm we will put all the things together and then the final version of the algorithm can be drafted so what has happened now let us draw two pictures this is yes and this is V minus s and there are several vertices U Is Here There is a V and then we have moved V over

here so yes and V has been moved here okay this is small yes this is the set yes now you take let us consider two vertices one is u another is U Dash Okay so assume that you have uh uh U adjacent to V and U Dash is not adjacent to V okay so let us draw you in a more

comfortable uh way

this is V minus s this is V this is U this is U Dash and there are other vertices V to U you have an

edge and uh you are moved V so this is U and this is u-h and there are other vertices so after moving V this is the scenario okay now D of U and D of U Dash what is the meaning of d of U Dash it is a minimum weight among all the

special path weights by moving v no new special paths are created for U Dash the same set of uh special paths continue to be there here because adding V is not creating any special path for U Dash Okay however for you a new special path is created that is because we has come here now s Tov you have a

path special path you have moved V also here so that path has become a special path to you now okay therefore now I have to update D of U I don't have to worry about D of U Dash I don't have to worry about D of U Dash but I have to examine D of youu

because for you some new special paths have come into picture I have a minimum among the old set of special paths a new special path has come maybe this is shorter than the other one how do we know what is the length of or what is the weight of this new special path it is

DV because this is the path and plus weight of v u DV plus weight of V this is the weight of new special path to you this is the weight of a new special path to you whether this new special path is updating the minimum how do we check if D of U is greater than D of V plus weight of

UV then the new special path is the minimum special path it has got a smaller weight then D of U is updated to D of V + W UV and now this is the updated uh shortest special path the previous vertex so previous of you equal to V so you can see that this is the previous

vertex to U in this picture U is attached with v earlier somebody else some other path was defining the minimum and that might be the uh previous vertex now this path is defining the minimum special path or shortest special path therefore the previous of V is U all right this I have to do only for

Neighbors of V if a Vertex is not even uh a neighbor of v i don't have to worry about them for those vertices the du- value remains same d U Dash where u-h doesn't belong to adjacency of V does not change and if U is in the adjacency of v it may change if this is the condition

if it is defining a new uh therefore what is the updating uh code if uh so

uh for All U in adjacent C of V only for this vertices I will consider for every vertex adjacent to V that is in V minus yes so for all you If U belongs to V minus s and this condition uh D of U is greater than D of V plus weight of

v u if this is the case then D of U is equal to D of V plus weight of Vu and uh P of U equal to V that's all is the updating uh uh to be done so let us see all these things are done assuming a d value is available so how will the D values uh

look like initially we have to initiate the D values properly let us start with the following simple initial configuration okay we will have in yes only the vertex s and then here all the vertices V minus s okay consider a Vertex V here what is a special path to be special path is starting from yes it

will go through all the vertices of yes and then with a Crossing Edge it will reach V that is a special path right there is no other vertex in yes therefore the special path is nothing but the edge there's only one special path its weight is so the edge SV is special path to V from s this is the only one so

weight of the minimum weight of special path is D of V is nothing but weight of SV suppose that there is a vertex U that is not adjacent to s from s to U there may be paths but there are no special paths because there is no Edge connecting yes to you because

special path means all vertices must be in this set to you from yes there may be paths but there are no special paths so if you doesn't belong to adjacency of s then no special path exists at this point from yes because s has no other vertices therefore special path means it should be a nedge when a special path

doesn't exist we always set Infinity okay therefore this is the initial uh configuration the initial configuration is D of V equal to weight of yes V if V belong to adjacency of s this is equal to Infinity if the vertex is not in adjacency of yes okay I'll write it cleanly is equal to

Infinity if we B doesn't belong to adjacency of yes this is the way you initialize and D of s is zero so D array is initialized like this and uh what about the previous array previous of yes not only yes okay previous of yes is

undefined previous of V equal to yes if if V belongs to adjacency of yes because you have a special path okay look at this situation previous of V is yes in this picture you can see that previous of V is yes previous of U if it is not adjacent it is not defined there is no path and is

undefined if uh V doesn't belong to adjacency of s so this is how you initialize d array and P array okay how are you going to represent the partition the split yes V minus yes because we have to often check and we have to move from one set to another okay we represent s vus s by a Boolean ARR

let us say in yes in s v = to 1 if V is in s because in yes equal to V equal to 1 if and this is zero if V is not in s okay it's a bullan ARR it's a flag indicating it is in yes or not okay therefore this implies in s of V equal 0 for V in V

minus s because vus s means these are the sets that are not in yes therefore if you want to check whether uh vertex is in V minus s you have to look into this Boolean array you just see whether in s of V is zero if that is the case that vertex is in V minus

yes okay so how do you move a Vertex from v- S 2 s how do you move how do you implement that movement okay in picture we are drawing around and other things but how computational a computer program has to do it mathematically so it's very simple if it is in V minus s in V will be zero

okay so set in s v equal to 1 so earlier it will be zero because it was in V minus s now it has been moved means it is in yes how do you know that how will the program know that a Vertex is in yes this Boolean array value will be set to one

that's all this implements moving of a Vertex from V minus s to S okay so

dtra G equal to v e uh W yes given this as an input it has to uh produce for each V the Delta V okay the Delta V will be available in an array called D okay uh in the end uh d v will be equal to Delta v as output and PV

is the pre previous vertex to V in the shortest path in other words p v v is abelman Ed okay initialize D array and P array we have seen how that is done okay two find a Vertex V in V minus s such that D of V is less than or equal to D of U for

All U in vus s so for each vertex in V minus s you look at the D value and uh find the minimum there will be some vertex for which the minimum value so by scanning the Dr array only for the elements of V minus s we can find the vertex V with the minimum D

value third step is move V uh uh 2 yes move uh V2 yes okay you have to initialize DP and uh here itself let me specify yes vus s you have to initialize s vus s how do you initialize s vus s you put only the source vertex s this source which is a

part of the input put that in yes all other vertices in V minus yes okay uh but how do we actually do that we have a bullion array for that so let's see how this is okay let me see whether I have space in the previous page ah okay so

initializing initialize S V minus S as the single t s and V minus yes so in s of s equal to one because this one is included in yes and in yes of V equal to 0 if V is not equal to s for all other vertices you set nsv equal to Z for S

you set NSS as one this represents the partition this represents the initial partition for the initial partition you know how to initialize D you know how to initialize P these are all the ways in which you have to initialize D and V for okay so initial is d p SV minus s after

that find a vertex in v such that D of V is less than or equal to move V to S we have seen how uh moving of V is to be implemented the fourth and final step is update D value and P value for every u in V minus s we have to update

this although in the pseudo code I have written update D of U and P of U for every vertex you don't have to really touch those vertices that are not adjacent to V because only V has moved to s so this step is expanded like this we expand step four as follows okay

if U belongs to adjacency of v and D of U is greater than D of V plus weight of Vu then you update D of u d of U equal to D of V plus weight of v u and P of U equal to P of U is equal to a v therefore fourth step is executed only

for the Neighbors of V adjacency of uh V okay so this completes the specification of Dyas algorithm the complete specification of the D algorithm is here we have put all the ideas that we have developed in bits and pieces and uh integrated them and uh given in this pseudo code so this is

what you have to do uh after initializing you have to do two 3 and four repeatedly okay so we have to do two three and four repeatedly that uh is not mentioned here I will mention now uh so uh basically we will um uh we will do like this I'll create a space

here this is a single pH so one initialize d uh initialize the partition s vus s based on this the D array and P array then while yes is not equal to v v is the vertex set while s is not equal to V you repeat 2 3 and four okay so you can perhaps call this as step

two it's easy to visualize that way

you call this while loop as step two and finding this vertex as within the Y Loop 2 a moving this as 2B because this is all in the while loop and update du is 2 C we expand Step 2 C

as follows okay just we are fitting in 2 c as follows so this will be in the while loop after the while loop the third step return D array and P array okay so we will write like this return D of uh V and P of V for all V belonging to V this is output that we

want comment uh D of V is in fact Delta uh V and PV V is the bman edge so this you can use to actually construct the shortest path okay so this completes the description of daas algorithm we will now take a quick look at uh the complexity of this method okay notice that yes initially had only

one uh vertex and you are moving one vertex in each iteration therefore the while loop of step two will be executed n-1 times what is n cardinality of V equal to n initially s has got only one vertex and in each iteration of the while loop you are adding one vertex to S you are

finishing when s equal to V that is when all vertices are included in V that is for all vertices when I know the shortest path weight I complete so n minus one vertices are to be added therefore n minus1 iterations are to be done therefore while loop will be executed n minus one

times okay in each time you are finding the minimum element in 2 a 2 a what is the cost of 2 a you have to go through all vertices in V minus s and find the minimum initially V minus s has got n minus one elements then n minus 2 elements then n minus 3

elements and so on therefore total sum of cost of 2 a across all iterations is n -1 + N - 2 which is order n² total sum of our total cost of 2B across all iterations is is n minus1 because in each iteration look at 2B 2B is moving V2s moving V2s is done by setting the

Boolean flag to one that's one step right therefore 2B when you implement nus1 times the total cost will be n minus one what about 2 C in 2C you are doing work proportional to the degree of or out degree of V okay so total cost of 2 C across all iterations is equal to sum of out

degree of v v belongs to uh V minus yes okay you know that the out degree sum is nothing but uh M right number of edges total number of edges recall from our introduction that the outdegree sum is exactly equal to the total number of edges that implies the total cost of 2 C

across all iterations is order M therefore the complexity of dxas [Music] algorithm is order n² + m okay this is a very simple implementation very direct implementation we don't have any sophisticated we we did not employ any sophisticated data structures we just used arrays to maintain the information that we uh want to use and uh searched

in the array to find the minimum V and updated the array by changing the values okay all these things are done in a very simple manner this simple implementation has a complexity order n square plus M there are some interesting data structures that we can employ and improve the complexity of this algorithm

the algorithm is same but instead of maintaining the information of the vertices in V minus s in a simp Le array instead of maintaining in a simple array if you use Heap or Fibonacci heaps it is possible to improve the complexity significantly and uh that is what we are going to look at in the discussions

related to this in the next session thank you