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 14 Bellman Ford P1 — Transcript · YTtoTranscript

Home/Transcripts/YouTube

YouTube Transcript

Lec 14 Bellman Ford P1

NPTEL - Indian Institute of Science, Bengaluru · 2,173 words · 11 min read · EN

Watch on YouTube

Share X LinkedIn WhatsApp

Below is the complete, readable transcript of Lec 14 Bellman Ford P1 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 will now begin our discussions on Bellman Ford algorithm so we are going to work on a graph G which has a verx set V Edge set e weight function W yes Source function yes we are interested in solving single Source shortest path problem that means we have to find out Delta V

and uh uh parent of V for every vertex V towards this we had a mathematical formulation and obtained belman equations uh for the Delta values but they have nonlinearity and circular dependency see okay nonlinearity and uh circular dependencies these two things made solving the Belin equation impossible so we were looking for an iterative way to

solve the belman equation and obtain the Delta values towards that we have introduced uh the quantities like Alpha i v and Delta i v and we are going to iteratively build a solution we're going to still work towards obtaining the solution for belman equation but then in the same equation we are relating Alpha

I values okay and uh we have derived belman equations for bounded walks and bounded paths that means there is a bound on the number of edges this leads to a decreasing sequence leading to the answer we are looking for so we have Alpha 0 for all vertices using that alpha 1 for all vertices and finally we will end

up alpha n minus one for all vertices this is an iterative process and that is what the bman and for algorithm is going to carry out basically the bman and for algorithm will keep Computing the alpha values if G has no negative Cycles then whatever we are Computing turns out to be Delta 0 to

Delta 1 to Delta 2 and so on to Delta n minus1 this computation is valid for any graph but if this computation is carried out on a graph that has no negative cycle the computation that we are doing values we are generating are indeed this that is because for such a g Alpha

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

i v equal to Delta I V for all V that is the reason why uh our computational process or whatever belman and for is doing is leading to an answer why does it lead to an answer Delta n minus1 we is in fact equal to Delta V so the answer we are looking for is obtained through a method

of iterated improvement or successive approximation so when we are unable to solve directly we use the powerful mathematical idea of method of iterated improvement in our context the method of iterated improvements are achieved through the alpha values we will see the details V is less than or equal to Alpha i - 1 U plus weight of U

V for all edges UV Alpha IV is less than or equal to Alpha I minus not only this you also have the following fact Alpha IV is equal to Alpha i- 1 U plus weight of UV for some Edge UV for some Edge UV this is also true that means Alpha i v is equ Al to minimum

over U not equal to V of alpha i- 1 U plus weight of UV okay so this is the belman equation for bounded walks you can call this as bman equations for bounded walks what we mean by bounded means the number of edges it's limited we are considering only the walks with less

than or equal to I edges here that's why these are called bounded walks in general your walk can be unbounded any number number of edges can be there but we are focusing on the walks with the bound on the number of edges and Alpha i v is less than or equal to Alpha

IUS 1 U plus v u and it is this so we are not able to solve the belman equation for deltas that is because the belman equation for Deltas have circular dependency but you can see that the belman equation for the alpha values they do not have circular dependency you can smoothly proceed look at the

dependency Alpha I is depending on only Alpha I minus one so if I have Alpha I -1 yes Alpha I -1 another ver vertex alpha i- 1 yet another vertex and so on somewhere Alpha IUS uh 1 uh U right Alpha IUS 1 U I have Alpha I values using this I can

get Alpha I values

all Alpha values are depending on Alpha IUS one values that means from the values in the array Alpha ius1 we can uh by using let's use y from let's by using the values in the array Alpha IUS one we can compute the array of values Alpha I it's an array okay all values so you have n values in Alpha

minus one array one value for each vertex and you compute uh so how do we uh compute this here is a very simple pseudo code based on the equation belman equation that we have uh seen okay here is the belman equation I will show once again okay here is the bman equation So based on this bman

equation we have to uh so this is what we are going to do every Edge has a potential to improve the alpha value of uh some uh V especially U v may uh improve right the value of alpha IV therefore here is the Simple Plan pseudo code to improve okay pseudo code to

compute Alpha I array based on Alpha ius1 array values based on these values how do I do that first of all I will set Alpha i v is equal to Alpha I -1 V because either it is this value or probably smaller value remember it is hierarchy so the bigger set minimum either the minimum of

the smaller set or it could become smaller let's see whether it is becoming smaller Alpha I equal to V this is step one for all V first copy the array value Alpha i v to Alpha IUS 1 V to Alpha i v then for each Edge u v uh do it in the next page so I'll cut

this uh Computing Alpha IV values by using Alpha i-1 array values how do we do that Alpha i v is equal to Alpha i- 1 V for all V belonging to V this is step one and step two for each U V in E for each Edge UV in E if Alpha i v is greater than Alpha i-1 U

plus weight of UV that is you have found a smaller value because you have found a smaller value you have to update it to the smaller value that is the way to find the minimum the way in which we find a minimum is we keep scanning the values when we find something smaller you

replace with a smaller straightforward logic of finding the minimum if Alpha IV is greater than Alpha i u plus UV then Alpha i v equal to Alpha i - 1 U + W UV and we have to save the belman edges so the current belman Edge is The Edge UV which is changing the

value we have already seen that we are going to use a Convention of previous P array notation because bman edges are always lost edges and in the last Edge u v u is going to be previous to V therefore in this Edge UV therefore previous of V equal to U this is Bellman

Edge this is actually actually current we will write it as current bman this bman Edge will get updated current belman

Edge when the loop terminates Alpha i v will have the minimum and P of V will have the previous of the last Edge it will have the belman edge proper bman Edge ending at P so when the loop is terminated when step one and step two are done after this Alpha IV will

have minimum over because minimum over U not equal to V of Delta U plus weight of u v uh sorry not Delta my apologies it's Alpha ius1

Alpha IUS every Alpha array is fully consulted wherever there is a u and an edge UV this value is computed and minimum the smaller value is updated therefore it will have the minimum Alpha I will have the minimum and p v v is The belman Edge ending at V and pvv is The belman Edge ending at V

uh maybe I I will write this cleanly next uh page so that uh I will erase it this can be edited one second so what is the consequence of executing the consequence of executing is Alpha i v is equal to minimum over U not equal to V of alpha i-1 U plus weight of

UV this is a correct value that we want and p v v is the bman ending at we you have a current bman yet but that was updated finally when when you finished with Alpha I will have the correct value and pvv is The bman Edge ending at V so this is called the Improvement step

this is called Improvement step Improvement step it improves Alpha I vector or array of values to Alpha I array of values Alpha I minus one array of values let's pass a moment to find out what is Alpha 0er okay let us see Alpha 0 array what is Alpha 0 yes it is the length of the

walk from s to s from s to S with Maxim maximum zero edges that is no Edge at all maximum number of Edge at most zero Edge means no Edge from s to S you have to go without using an edge zero what about Alpha 0 V for all other one from s to V you have to go without

using any Edge maximum zero Edge you are allowed there is no such such walk if there is no such walk it is infinity therefore this is alpha0 you know how to compute Alpha minus 1 to Alpha I therefore use this Improvement Step n -1 * from alpha0 array build alpha 1 array from alpha 1 array build Alpha 2 array

in this way you keep building it until you get alpha n minus one array alpha nus one array you built how do you go from one array to another array the Improvement step that we have shown okay the Improvement step that we have shown here okay tells you how to go from alpha

IUS 1 to Alpha I now so from alpha 0 you go to Alpha 1 and to and you stop here alpha n minus1 so you have Alpha nus1 Vector that means Alpha n-1 yes Alpha nus1 for another vertex alpha n minus1 for at another vertex so in in this way you have alpha n minus

one for all vertices you have since G has no negative Cycles or zero Cycles this is nothing but Delta nus1 yes Delta n-1 whatever is that vertex Delta n minus1 this is nothing but the because we know that we have already seen that Alpha I equal to Delta I if G has no

negative Cycles but Delta n minus1 is nothing but Delta therefore Delta s is computed Delta of this vertex is computed Delta of all all vertices are computed in other words single Source shortest path problem is solved you can see that when we were trying to find the Delta values directly when we were trying to

find the Delta values directly using belman equation we were caught in a mess there was cyclic dependency and we were not able to get it but now we are getting the Delta values in a different way we are using Bellman like bounds for bounded walks those bounded walks have got nice relation which is

very easy to compute in one go you can start from alpha0 and go to Alpha 1 from alpha 1 you can go to Alpha 2 so you are able to go and finally you get alpha n minus1 for every vertex alpha n minus one for every vertex is nothing but Delta nus1 for that

vertex okay we have seen that Alpha nus1 V is nothing but Delta nus1 V Delta n minus 1 V is nothing but Delta V because no path can have more than so you have solved the Delta V for all V by taking a slightly different route okay very impressive isn't it you were

stuck at a method for finding the Delta directly but we used another method in that method we have proceeded iteratively and we have reached the Delta values through an iterated improvement process okay so we will uh uh this is a right point to break thank you