So guys, now I will show you that given an input graph, how can you run SBF algorithm on the graph
in order to compute?
The result.
Right.
So I hope you have already revised the Dijkstra algorithm from the textbook.
So a typical Dijkstra or shortest path algorithm consists of the following three steps.
That is, evaluate neighbors the least cost node from the priority queue.
And the step number three involves the record result.
Right.
So to start with, you can see that you have a network topology as shown here.
Now, this network topology is actually a graph data structures which exist in the local memory of the
routers.
So it's a graph data structure which represents a physical topology.
But this particular graph data structure exists in the local memory of the node as why nodes?
Because we will going to trigger SPF algorithm by assuming that the node as is a source node.
So our goal is to compute the shortest path to every other node of the topology from the node as.
So to start with, let us talk about initialization of SPF algorithm.
The initialization of SPF algorithm involves two things.
The first thing is that that the source node will mark every other node in the topology, as if those
nodes are infinite distance away from the source node.
S Right.
And the second thing is that that the source node s will mark itself as zero cost away, right?
So this is the first part of the initialization.
Now the second part of the initialization is that that the source node s would compute the next hop
information for its directly connected neighbors.
So for the directly connected neighbor A the next hop information would be following that is outgoing
interface would be Ethernet one, the gateway or the next hop IP address is 2.2.2.2 and the next hop
node is eight.
Similarly, the next hop information for another directly connected neighbor is the following Right
now this next hop information is stored in the node A itself, and this next hop information will be
stored in the Node D itself.
So this was the second part of initialization of SPF algorithm.
Now, Dijkstra algorithm uses an internal data structure called priority queue.
You can implement this priority queue as a minimum heap.
Right now we will going to execute the shortest path first algorithm starting from the node s.
So, guys, the execution of the SBF algorithm mainly involves three steps.
The first step is the evaluation of the neighbors.
The second step is the least cost node from the priority queue.
And the third step is recording the result of the node, which has been just removed from the priority
queue.
So we will going to apply all these three steps on each node of this input graph.
Now we are starting the algorithm by taking the node s as the source node and we will compute the shortest
distance of each node of this graph from the source node.
S.
The result of the SPF algorithm will be stored in this table.
So the first step of the SPF algorithm says evaluate neighbors.
Right now, the current node to start with is the source node s, So we will going to evaluate the neighbors
of the node S.
So now to evaluate the neighbor of the node as what we will going to do is that we will add the metric
of the current node, which is zero with the cost of the link which connects its neighbor node that
is three.
And we will compare with the cost of the neighbor node, which is currently infinity, right?
So it simply means that zero plus three is less than infinity.
Therefore the new cost of the neighbor node A will be three.
Whenever we explore a new node in the input graph data structure with a better cost, we will going
to add that node in the priority queue.
Right.
Similarly, the second neighbor of the node s is D and the cost of reaching the neighbor node D from
the source node s is four, so the cost is reduced from infinity to just four.
So therefore we will going to add the neighbor node D in the priority queue.
Right.
So we are done with the evaluation of neighbor of the source node.
As now second step says that the least cost node from the priority queue now in the priority queue,
there are currently two nodes A and D and A is the node with the least cost, which is three.
So we will going to remove the node a from the priority queue.
Right.
So this completes the step number two.
Now we will going to record the result of the node, which has been just removed from the priority queue.
In this case, the node, which has been just removed from the priority queue is the node A, So we
will going to record the result for the node.
A Right.
So in this diagram you can see that the next hop information for the Node A is the following, right?
So write it down in the table that for Node A, the outgoing interface is Ethernet zero by one.
The gateway IP address is 2222 and the cost for reaching the node A from the source node is three,
and the next hop node is a itself.
Right?
So this is what we mean by recording the result for a particular node.
And therefore with respect to the node A, we are done with the step number three.
Now we will go back to the step number one and now we will evaluate the neighbors of the node A.
So you can see when we evaluate the neighbors of the Node A, so B is the neighbor of the node A, which
has now been explored with the better Matrix seven.
Right.
So whenever a node is explored with a better metric, we do two things.
The first is to place that node in the priority queue.
The second thing is that that the node B has been explored from the node A with a better metric.
Therefore, copy the next hop information of the node A to the node B.
Similarly, the other neighbor of the Node A is the node D, but if you try to explore the node D from
the node A, the cost for reaching the node D from Node A will come to eight.
That is three plus five eight, which is inferior to four because Node D has already been explored with
the cost four from the source node.
S.
Right.
So in this case we will not going to take any action.
And the same applies when we explore the node s, which is the neighbor of the node A from the node.
A Right.
So in that case also we will not going to take any action.
The cost for reaching the node as from the node A is three plus three six, but node s is already reachable
from the source node s with the cost zero.
Right.
So again, we are done with the step number one.
Now, step number two says that the least cost node from the priority queue now in this case the least
cost node is D, right?
So now we will going to record the result for the node D.
So you can see that in the diagram for the node D, the next hop information is the following.
So therefore record this result, right?
The outgoing interface will be Ethernet zero by two.
The gateway IP address will be 1111.
The cost is four and the next hop is D.
Right now we are done with the step number three.
Now we will going to explore the neighbors of the node D.
So again, in this diagram, if you explore the neighbors of the Node D, then C is reachable from D
with the better cost.
Ten.
Right.
And A is reachable from T with the cost nine.
Therefore, we will not going to take any action and s is reachable from t with the cost eight and therefore
we will not going to take any action.
Right?
So we were going to play C in the priority queue because we have just explored C with a better metric
and because C has been explored from the node D, therefore copy the next hopes of the node D into the
node C Right.
Now again the least cost node from this priority queue.
So in this case the least cost node between B and C is B.
Therefore we will going to record the result for the node b.
So you can see that the next hop information for the node B is same as the next hop information for
the node A Therefore we will going to record the result for the node B.
Right.
So now we are done with the Node B also.
And now we will going to evaluate the neighbors of the node B, right?
So neighbors of the Node B is A and C, so C is reachable from B with a matrix seven plus 1017, which
is no better metric.
Therefore we will not take any action and a is reachable from the node B with cost seven plus four,
which is 11, which is again an inferior metric.
Therefore we will not going to take any action with respect to the Node B's neighbor.
Therefore we will not going to push anything into the priority queue and now we will again dequeue the
least cost node from the priority queue, which is C because C is the only node present in the priority
queue and we will going to record the result for the node C so you can see that the next pope of the
node C is this one, right?
So just record the result.
So this is the result for the Node C and now we will going to evaluate the neighbors of the Node C,
right?
So here again, you can see that if you evaluate the neighbor B from the node C, the cost will be ten
plus 1020, which is inferior metric, right?
And if we evaluate the neighbor D from the node C, then the cost will be ten plus 616, which is again
an inferior metric.
So we will not going to push anything in the priority queue.
And, and SPF algorithm terminates when its priority queue becomes empty, Right?
So it simply means that we are done with applying the SPF algorithm on this input graph.
And we have computed the next hop information as well as the shortest path cost to reach each node in
the input graph from the source node.
As So this is how SPF algorithm works.
I would suggest you to again do self exercise and dry run or apply the algorithm and practice it more
and practice it more by applying on this input graph.
Now, in the next lecture video, let me take one more example for applying SPF algorithm so that you
understand it better.