[MUSIC].
Good day viewers and in this segment we'll talk about Dijkstra's algorithm for
computing shortest paths this way the computers do the calculations instead of
us which is generally a good thing. So the figure down below here shows an
example of a network topology. What we'd like to be able to compute in
this network topology is the source tree from a particular load.
Like, for instance, E out to all of the other destinations nodes in the network,
or the other nodes as destinations. This will allow us to work out the
folding table for E, or which way to go to reach all the different destinations.
If we can do that, You know, we’ve solved the forwarding problem.
Dijkstra’s algorithm provides one way of computing these source trees and it’s
widely used as part of a common routing protocol, which is why we’re covering it.
Dijkstra’s algorithm is named after E.W. Dijkstra, a famous computer scientist.
He, is well known for his contributions to programming languages.
You might have heard of a, a paper called Goto Considered Harmful.
That was him. He's also made many contributions to
distributed algorithms such as the algorithm we'll study, computing shortest
paths as well as program verification. So, Dijkstra's algorithm that we'll look
at dates from 1969. So it's been around for a while.
It's, a single-source shortest paths algorithm.
Which means that, it takes a given source, and from that source, it computes
shortest paths to all the other nodes in the network.
To do this, it needs to know the network topology.
And there's also a caveat, a little restriction here.
All of the link costs that are on the various link networks need to be
non-negative. This is usually perfectly fine for for
using network graphs because, if the quantity's, the costs, correspond to
anything physical or meaningful, chances are they're non negative anyhow.
Okay, so here's an outline of the algorithm.
I'll go through this outline and then we'll work through an example so you can
see it in action. So the first of all, is an initialization
step, Dijkstra's algorithm is going to visit all of the nodes.
So we begin by marking all of the nodes as tentative.
And we set up distances for them. All of the nodes are keyed by their
distance. The distance of the source from which we
want to compute the shortest paths from there out to everywhere else is set to
zero, and the distance of all the other nodes we'll initialize it to be some
constant that means infinity, we don't know how to reach them yet, and then we
proceed in this main loop. This main loop says while there are any
nodes which are tentative, meaning that the algorithm hasn't them yet, how they
fit in to the source tree. Then what we will do is we'll extract the
node with the lowest distance that we know.
We'll then add that node to the source tree by drawing a link from wherever it
was used to get its current distance to the node.
And then we will we will use the information from that node to relax other
cost, to lower other cost. We do that by taking the cost of the
node, looking at the nodes neighbors and seeing if the, is a lower distance way to
reach any of the nodes neighbors. That might sound a little mysterious.
But let me go through an example and you'll see that this relaxation step is
quite straightforward. OK, here's an example that I'm going to
walk through. It's the same typology from before and
I'm showing where the initialization fails, where you can see that next to all
the nodes are written in red they cast from many nodes it's infinity.
For the source we'll going to start from it's zero.
Now proceed for that wire loop. First step for the wire loop.
we going to take the node with the lowest distance its A where we want to start
from into a relaxation around A. So if A now has cost 0, we can see I
changed the cost to blue, its locked in, once we visited the node and taken it.
Then we found the path to that node. Then, the the of course this is just the
source. Now, I'm going to color nodes that we
visit black and then the relaxation from here it looks the cost of this node, 0,
visits all of its neighbors. And sees if it can lower the cost.
What are its neighbors, of a? One is b, you can see here I've circled
b. B's cost used to be infinity, but b is
one link of cost four away from a, which is cost zero.
Therefore b's cost could be reached via a cost four.
That's less than infinity. So we're going to lower the cost from B
from infinity to four, that's unrelaxation.
We'll do the same thing for E, E's cost use to be infinity when we didn't know
how to get there, but now we have an option we can go from A to E directly
over this link will cost 10 so E's cost will be 10.
Both these modes will be relaxed, that's a step in the right direction.
Next iteration what do we do we pick the next lowest node that's going to be b
with cost four just circle b. So we add b to the shortest path tree.
From the source tree from A. Now B with cost 4 was reached from A
directly over this link, so we add that this link to the shortest path tree.
Now let's perform a relaxation. We'll go around all of the nodes
connected to B, and see if we can use the links for From B to lower the cost.
Let's look at C first. C's cost used to be infinity, but C is a
link of cost to or away from B at cost 4, so C can go down to cost 6.
It got lowered. E, well E is a link of cost 4 away from
B, so that can be reached at 8. These costs before used to be ten so
actually e has now been lowered to be cost 8, so interestingly e,s distance has
fallen not just form infinity down but it used to be some finite number 10, now it
has gone down to 8, so we're finding better parts over time as we go out
further and further away from a. Similarly we'll do the relaxation for f,
sorry, the relaxation from b. When we look at its neighbor f its cost
goes down to 7 and g goes down to 7 too. This is great.
Okay, next step. What do we do?
The next lowest cost, well, the lowest cost of the remaining nodes that haven't
been visited is c would cost 6. So we take it, I've changed it's cost to
blue, so say that it's, it's done. We add this link.
See with cost six could be reached with that cost from B.
So we add that to the tree. That's a new link.
I've colored C black to indicate that no one's visited.
No we do my relaxation around C. What's going to happen?
Well, H's cost is going to fall. we have the cost of D can be reach now,
at 8, here. So, I think D's cost has fallen too.
I'm not sure, we'll see that. I, I, I guess well you have to look at
the previous slide. relaxing from, relaxing from C we get
that the cost of E has now gone down to 7 because it can be reached over a link of
cost 1 from C to 6, when plus 6 is 7. So it's going down again Well our route
to E is just getting better and better. yes D, I guess D went down from, well, I
don't know. You can, you can look at the previous
slide. It's hard work going through these
graphs. I hope I haven't made too many mistakes
that you're going to find. Okay, so continuing, well, it looks like
actually we've done all the relaxations for C.
So let's continue on. Now we're going to pick the next lowest
node. There are actually three nodes that have
caused seven. So any of those will do as the minimum
cost to extract. We're going to arbitrarily pick g just to
work our way around the graph. G could be reached at cos 7 from b, so
we've now added this link here, to the shortest par tree out from a.
And I've changed the cost to G and 7 to blue and marked the no g in black.
Let's do the relaxation from G. G has one other neighbor so that other
neighbor we can reach O in a link across 4.
So the cross to reach F by G would be 11. Eleven is not bigger than seven, so
actually that means that rounding to F and G would be a bad move.
And we don't lower the cost. And remember that is a new root.
So that hasn't changed anything. Next moving on, we'll do our relaxation
around F. So first of all we're taking F as the
next lowest node. We're going to add the link but at which
F was reached across 7, to the shortest path tree, that is a link from B, which
reach from B across 7. And so we added this node to the shortest
path tree. We do the relaxation, and we find
actually that it doesn't lower anyone else's cost.
Everyone else has reached a better way than going through f I guess is what that
means. Continuing, now we get to e.
So we want to do a relaxation around e. So we take E, make its cost in 7 is not
in blue. We colored the node black.
We've added the link E at cost 7 was reached by C.
So we add this line from C. to our shortest path tree.
Now as we do that relaxation, I think nothing much changes, because all, by the
way, all of these nodes that are already being visited, that are in blue, they're
not going to change. We found the lowest cost point way to
reach them. The only node that could potentially
change is this one in red, that 7 plus 2 is 9.
That's bigger than 8. Doesn't change.
Okay, going on, what's left? D.
D now will take that as the next lowest. And we will take this link, to D.
We added that relaxation doesn't change anything.
And finally, there's one node left, that's H, it cost 9, so we add this one.
And we're done. We've now found the source tree from A to
all nodes. If you just look at all of these blue
lines you can see that they start at A, they go out and they provide a set of
paths to reach all other nodes on the graph.
And these are the least crossed paths through which any of these other nodes.
So we've done it, we have a nice, methodical procedure for finding this
source tree from a given node, for a particular topology.
And that's Dijkstra's Algorithm. Then we'll make just a couple of comments
before we wrap up. So, you might have noticed that
Dijkstra's algorithm finds the shortest paths in order of increasing distance
from the source. What it's really doing is leveraging this
optimality property, that for long shortest paths to smaller shortest paths.
Sub paths are also shortest paths, so we can build up from small paths to large
paths and they all overlap. And that's why it works to go out at
increasing distance and then insures that once we've gone out to a certain
distance, we'll never change our mind later.
And change any of the path we've already selected.
This algorithm can take a little while to run on a graph tolopolgy.
Actually the efficiency of running it depends on how you implement this extract
minimum cost node function. Depending on what data structure you use,
you can use different ones depending on if your network is dense in edges or
sparse in edges. but in any case the running time is super
linear in the size of the network. That means as the network grows larger
the run time of this algorhitm is going to go even more quickly and
eventually if the very large network the run time would get very large.
It's not surprising really there are so many different little paths that you can
you can easily imagine some of the complexity and finally, I'll note that it
gives us the complete source tree or sync tree depending on which way you run it.
This is actually more than we need for [UNKNOWN] Each node destiny needs to know
the next hop for our particular destinations.
So we have more than we need for forwarding and we can it, it's, that's
great. To get this, of course, we needed to know
the complete topology, so that's going to be an issue we'll have to address in
routing. Okay, now that we know Dexter's
algorithm, I think we can keep moving on and look at all that.
Routing algorithms.