So, guys, now let us apply SPF algorithm on one more input graph data structures so you can see that
on the right hand side, this is the input graph data structure and node s is the source node.
The cost of every link in this graph is one, and the initialization part of the SPF algorithm is already
done.
We have computed the next of information for directly connected neighbors of this source node s, and
every node is presumed to have been reached with the cost of infinity and the source node s is reachable
from the source node as with the cost.
Zero.
Right.
So to begin with, the initial state of the priority queue is empty.
And the first node that we will going to explore is the node s.
Right.
So the neighbor of the node S is A and T, so the cost of reaching the node A from the S is one, and
the cost of reaching the node T from S is again one.
Right.
So since these are directly connected nodes, they already have their respective next hops.
Now we will going to add the Node A and D in the priority queue because we have just explored them with
a better metric.
Now take out the node with the least cost from the priority queue since there is a tie.
Therefore you can pick up any node.
Right.
So let's say I pick up the node A and now I will explore the neighbors of the node A.
So B is reachable from A with the least cost two and D is reachable from a with the least cost two.
Therefore I will ignore it and I will always ignore the source node s right.
So the only node that will make its way to the periodic queue is the node B with the cost to.
And because I have removed the node from the priority queue, I will going to record its result.
So outgoing interface will be Ethernet one.
Gateway will be 2.2.2.2.
The cost is one and the next hop node is a.
So the node has been removed from the priority queue.
Now the least cost node that is present in the priority queue is the node D, So I will remove the node
D and now I will going to process its neighbors.
Ah, one thing I forgot in the previous step that the Node B was explored from the node A.
Therefore I will copy the next hops from the node A to the node B right.
Now note this neighbor is the Node C and therefore it is reachable with a better cost to and therefore
copy the next hop information for the node T to the node C and push the node C into the priority queue.
Right.
And other neighbors of the node D that is s and a need not be processed.
Right?
So now, because we have removed the node from the priority queue, we will going to record its result
so its wife will be Ethernet to the gateway IP address is 111.
The cost is one and the next of information is D.
Now I will pick up the least cost node from the priority queue.
And now B and C both has the cost.
Two again, there is a tie, so I can pick up any.
So let's say I pick up the node B, right?
And now I will going to explore the neighbors of the node B So for node B two plus one is three.
Therefore.
S sorry, this is the node D.
Oh, sorry.
I have taken two nodes as in this input graph.
Let me rename this node to the node z.
Right.
So the node Z.
So here I will write Z.
So the Node Z is reachable from the node B.
A better metric, which is three, right?
So copy the next row of information of the node B to the Node Z.
And we need not process any other neighbors of the Node B because they are not reachable via better
metric.
So we will push the Node Z in this priority queue.
So we are done with the processing of the node B, therefore we will going to record the result of the
Node B and B's.
Next Hope is same as the A's next hope.
Therefore we will write Ethernet one, two, two, two two and the cost of reaching the node B is two,
and the next hope is a write.
Now the least cost node that is present in the priority queue is the Node C.
Therefore, we will going to remove node C from the priority queue and we will going to explore its
neighbors.
So for the Node C, you can see that the Node Z is reachable via metric three, right?
And Node Z has already been explored with the metric three, right?
So it means that we will going to copy the next rope for the node C to the node Z.
Right.
And Nodeset is already present in the priority queue with the cost three.
And we have just explored the node Z with the cost three.
So it means that we need not change the position of the node Z in the priority queue.
The other neighbors of the Node C need not be processed because they are not reachable via better metric.
So now it's time to record the result of the node C.
So Node C has the next hop information as follows.
The outgoing interface is Ethernet to the next hop IP address is 1.1.1.1.
The cost for reaching the node C from the source node s is two, and the next hop node is D, right.
Now the least cost node that is present in the periodic queue is the Node Z.
So we will going to remove this node from the priority queue and we will going to explore its neighbors.
So you can see that the cost of the Node Z is three and none of the neighbors of the Node Z that is
B and C are reachable via better metric from the Node Z.
Right.
So there is no need to explore any of the neighbors of the Node Z and now it's the time to record the
result of the Node Z.
So now you can see that Node Z has two next hops.
So one next hop is coming from the neighbor B and another next hop is being copied from the neighbor
Z.
So it simply means that Node Z will going to have both of these two as its next hops.
Right.
So let's record the result for the Node Z.
So I have recorded the result of the Node Z in the table and you can see that the Node Z is reachable
via this next hop, via this path.
And the Node Z is also reachable via this path from the source node s.
Therefore, Node Z has two next hops which are next hops.
So shortest path first algorithm automatically computes the equal cost multiple paths to destination
node if the paths exist at all as per the network topology.
So now it's an interview question for you that what is the time and space complexity for this algorithm?
Just pick up your textbook and try to understand the time and space complexity.
It is very important for the interview point of view.