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 12 Belman Equation Part 3 — Transcript · YTtoTranscript

Home/Transcripts/YouTube

YouTube Transcript

Lec 12 Belman Equation Part 3

NPTEL - Indian Institute of Science, Bengaluru · 2,334 words · 12 min read · EN

Watch on YouTube

Share X LinkedIn WhatsApp

Below is the complete, readable transcript of Lec 12 Belman Equation Part 3 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.

so if the graph uh has uh no negative cycle or uh zero cycle we know that the solution of this equation called belman equation is unique XV equal to minimum over all UV belong into to e of U + weight of UV it's a very interesting equation I know that it's a solution is what I want

but how do I go about solving this equation this equation has got circular dependencies we have already seen a small example in fact if the original graph has a kind of a cycle the variables which are depending on in that uh chain will display yes Cy Clic dependency if there is a cyclic

dependency things get messy and then when you have large number of equation you don't have any systematic procedure to uh solve this set of equations so after doing all this nice work finally we have in our hand a system of equations which are difficult to solve or there is no known procedure available

to uh solve them so how do we circumvent this situation so mathematicians have come up with a brilliant idea okay the method that they they approach they take whenever you see this kind of a nonlinear and complicated equations they take an approach called iterative

approach this also called as method of [Music] iterated improvements or method of successive approximations

this are all they all mean the same thing okay so what we do in an iterate approach is the following we start with some tentative solution and we find a better solution so we will have a method that is going to improve in some sense the solution in our hand so we start with a solution apply

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

that method get a better solution again apply the same method on the better one you got and you get much better one so in this way you keep improving the solutions so there is a basic method which will Define the so-called Improvement step and basic procedure is going to be repeatedly applied so you get a solution s0 from

that you get a solution S1 and from that you get solution S2 and so on okay each is an improvement over the previous one

so I'm not directly solving it I'm defining a procedure that will slowly take me to the solution okay so I'm taking a roundabout route I don't have a direct computational procedure to uh solve the equation but what I do is an iterative method okay a very clever uh approach if in numerical methods and in

various U other branches of uh mathematics we might have seen these kind of techniques what is important for us is that the this process of improvement should quickly converge in fact ideally it should converge in finite number of steps and that finite number should also be small so that we quickly reach the

solution the hope is that when you keep on improving it you get to reach the solution right this should converge to a solution all these things should happen in our context we are looking for the shortest path so what we can do is the following we start with some path do some computation and try to obtain a better

path and again do the same kind of a computation on that path and obtain a still better path or a shorter path so in this way we may plan to obtain a series of paths one shorter than the previous one with the hope that this process leads to the shortest path this called the method of iterated

improvement brilliant idea but then identifying um in what way we can achieve the Improvement and uh how many iterations we require all these things are technical details and uh we are going to take a look at uh them now okay so one natural way to go towards uh the solution is through what is known as bounded

paths we will find it somewhat difficult to directly deal with paths so we will go through what is known as walks bounded walks but bounded walks and bounded paths are related and we use all of that and finally solve the problem okay it's a very high level description we are going to see the details now

let w k v denote the set of all walks from s to V containing atmost K edges here we have K greater than or equal to Z okay set of all walks you can walk from s to v a series of edges end at V that series can have repetition and it can it's a walk after

all okay so w KV is the set of all but K is a finite number therefore this set is a finite set W KV is a finite set it could be empty but it is a definitely finite because the number of edges you can have is bounded that's why these are called bounded

walk you cannot have infinitely many edges here you can have only you are allowed to have only atmost K edges because it is a finite set each walk has a weight there is a walk with minimum weight all right let Alpha k v denote the weight of shortest walk in w k V okay this is the weight of the

shortest walk in W KV it's a number in our case it is an integer right what are the properties we can uh observe about this first of all notice that w k v is a subset of w k + 1 V okay why every path that has got atmost K edges obviously will be

in this set of walks that has got at most k + 1 edges a walk that has got less than or equal to K edges is automatically a walk that has got less than or equal to k + 1 edges okay a walk with atmost K edges is automatically you walk with [Music]

atmost k + 1 edges so every walk here every walk in W KV will be a walk in w k + 1 V every walk here is and w k + 1 v may have some more walks CU you may take a slightly roundabout and then reach V and thereby with k+ one EDG just there may

be a walk in which case uh this will be a super set otherwise it will be equal or it is a super set so you have a set B and you have a super set a what can you say about the minimum of these two suppose B is a set of numbers a is a

super set of numbers okay just numbers B is a set of numbers and so minimum of a will be less than or equal to minimum of uh B okay you you can put in this way also minimum of B is greater than or equal to minimum that is because every element of B is an element of

a therefore the smallest element of B is also there in a minimum of a is smaller than everybody so it will be smaller than even minimum of B that's all the simple logic very simple logic a superet of numbers probably will have a smaller minimum it will have the same minimum or it may have a smaller

minimum okay because of this you immediately see that Alpha k v is greater than or equal to Alpha k + 1 uh V it's a minimum over a bigger set a minimum over a bigger set may have a smaller minimum that is reason why this will be true that means we have a

decreasing sequence of values okay Alpha 0 V is greater than or equal to Alpha 1 V which is greater than or equal to Alpha to V and so on you have a decreasing sequence of values defined by this collection of sets this is a hierarchy of set it's a collection of set one containing other okay w k so

I have this set and then something larer and something and something bigger so in this way it keeps containing the previous ones therefore the minimums will form a decreasing sequence we are going to Define for paths similar quantities okay what are the let p k v is set of all p is a

path from s to V with utmost K edges of course K is greater than or equal to Z so here also we have the following p k v is a subset of PK + 1 V because a path with less than or equal to K edges automatically it has got less than or equal to k + 1 edges so that path

will be in the other set also so every element of pkv is an element of PK + 1 V PK + 1 v may have additional paths right so it's a hierarchy of set one containing the previous one now we are going to Define delta k v equal to the weight of shortest

path in P KV pkv is a finite set each path in pkv has got a weight therefore there is a shortest path minimum weight that minimum weight is delt k v that minimum weight is actually Delta KV the alpha sequence can be an infinite sequence but the Delta sequence is a finite sequence Delta 0 V is greater

than or equal to Delta 1 V greater than or equal to greater than or equal to Delta n minus 1 V and there it stops after that everything will be equal Delta NV is equal to Delta n + 1 1 V and so on this is not an infinite sequence it stops at n minus one you can Define

but all of them will be equal to Delta n minus one only it won't decrease any further why it's a path any path even the longest path cannot have more than nus one edges in a path no vertex and no Edge can be repeated therefore the maximum the maximum number of edges in any

path in a graph with vertex set of size n suppose vertex it has got n vertices what is the longest path n minus one any path you take from anywhere to anywhere it cannot have more than n minus one edges okay the maximum number of any path is nus1 that means every path is going to

have less than or equal to n minus one edges what does this mean every path will [Music] have only less than or equal to nus1 edges so p nus1 v is set of all paths this is set of all paths from s to V this is set of all paths from s to V

the minimum weight in that is the shortest path from s to V therefore Delta n-1 V is in fact Delta V you are finding the minimum over all paths and that is the shortest path okay therefore Delta V is Delta n minus 1 V what can you say about Delta NV set of

all paths with less than or equal to n edges this is same as because this itself contains all parts it cannot have any superet so all higher numbered indices are going to define the same uh set of paths okay because PN minus 1 V itself captures all paths okay okay so for example from s to

V this is a path of length one this is a path of length three okay if there is a path like

this 1 2 1 2 3 4 5 1 2 3 4 5 5 six this is a path of length six so you have various Paths of various lengths number of edges but none of them can have more than n minus1 that is the reason why you have Delta 0 V greater than or equal to Delta

1 V this can so this a path you have a shortest path among P1 shortest path among P2 shortest among P2 but shortest among PN minus one is the shortest path Delta n minus 1 V which is equal to Delta V and this is equal to Delta n v this is equal to Delta n + 1 V and so on

so this sequence becomes stationary here so you are going to when you are going to consider the shortest paths in these sets their lens become shorter and shorter initially you have this then you have a better path and you have so find the shortest path in P1 using this find the shortest path in P2 using that

find the shortest path in P3 in this way when you go you get shorter and shorter path after n minus one stages you have the shortest path in your hand method of iterated improvement okay therefore we have a high level plan where we are going to keep finding the shortest paths in this

collection which keeps giving us better and better paths there is a minor technicality here we will have some difficulty in working with the collection of paths but we can work comfortably in the collection of walks we can work in the collection of walks easily but working in the collection of paths is a bit tricky we

will see why we have introduced the alphas and Deltas our goal is to find Delta V which means our goal is to find Delta n minus1 but we are going to find Delta n minus1 uh not via Delta 0 Delta 1 Delta 2 but via Alpha 0 alpha 1 and so on and

then relate these two and get to our solution okay we will see the details of uh these in our next session thank you