So, guys, now that I have just demonstrated the first example of SBF algorithm, now let me discuss
formally the rules of the algorithm where the new node is explored.
By discussing the first easy example of SPF algorithm.
You must have now got some idea regarding how SPF algorithm works on an input graph in order to determine
the shortest path while at the same time computing their respective next hops.
So this diagram shows two nodes of the input graph data structure.
These two nodes could be any two nodes which are directly connected with each other with a link whose
cost is M right.
X is the cost of the node X that is, the node x is reachable from the source node as via cost x.
Right.
And node y is reachable from the source node as with the cost of small y.
Right.
Now, it is not necessary that the node y is reachable from the source node as y shortest path from
node x.
There could be some other node say, and the node y was explored from the node Z and Z in turn was explored
from some source node s.
Right.
I will just going to discuss that.
What rules do we need to apply when a new node y is explored from the node X right here, H1 and Ns2
are the next hopes of the node X and H1 and Ns3 are the next hopes of the node y which has been computed
by running shortest path algorithm on this graph data structure so far.
Now, somewhere in the middle of the execution of the algorithm, we are in the process of exploring
the node y from the predecessor Node X, right?
So this diagram actually represents the snapshot of SPF algorithm in execution.
And at this point of time, we are in the process of exploring this edge, Right?
So the case one says that if Node Y is explored from the predecessor Node X with a better metric that
is X plus M is less than Y, then we need to take the following action.
That is, remove the next hopes of the node y, copy the next hopes of the node X into the next hopes
of the node y.
Right.
And if the node y is present in the priority queue, then what you need to do is that you need to remove
it from the priority queue and add it back right by removing the node y from the priority queue data
structure and adding it back will allow the node y to take an appropriate position in the priority queue
data structure.
Remember, in priority queue data structure, all the nodes are maintained as per their cost.
This priority queue data structure is ideally should be minimum heap data structure.
Now the second case says that if the node y is explored from the predecessor node X with the same matrix,
it simply means that if X plus M is equal to Y, then in this scenario you need to apply the following
rules, right?
So you need to keep the existing x tropes of the node y copy the next hopes of the node X into the next
hopes of the node y and you need not copy duplicates.
So one is already present in the next hop collection of the node y.
So after copying the next hop ns2, the next hop set of the node y becomes an one and S3 and an H2.
Right.
So this is what the rule says.
Perform the union of the next hops.
If the node is explored with the same metric that is X plus M is equal to Y.
And the third rule says that if the node y is explored from the predecessor Node X with a higher metric
that is X plus M is greater than Y, then it simply means that you really don't have to take any action.
Right?
And we already have learned that the algorithm stops when the priority queue goes empty, right?
So these are the rules which allows you to compute the next hopes of each node of the topology when
they are explored from their predecessor node during the execution of SP algorithm.
Right.
Now, let us take one more example and let us apply these rules as we discussed.