Tip:
Highlight text to annotate it
X
>> [music] Good day viewers. In this segment we'll talk about
Dijkstra's algorithm for computing shortest paths.
This will let 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 node, like, for instance
E, out to all of the other destination nuts in the network, all of the other
nodes as destinations. This will allow us to work out the
forwarding 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. Dykstra'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 EW
Dijkstra, a famous computer scientist. He, is well-known for his contributions to
programming languages. You might have heard of a paper called Go
To Considered Harmful. That was him.
He's also made many contributions to distributed algorithms, such as the
algorithm that we'll study, of computing the shortest paths as well as program
verification. So, Dijkstra's algorithm, that we'll look
at, that dates from 1969, so it's been around for a while.
It's a single source shortest path algorithm, which means that it takes a
given source, and from that source, it computes shortest paths to all the other
nodes in, 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 links in the network need to be
non-negative. This is usually perfectly fine for, using
network graphs, because if the quantities, the costs, correspond to anything physical
or meaningful, chances are that 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, there 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 at
zero. And the distance of all of the other nodes
will 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 the
algorithm hasn't found 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 will 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 there 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 relaxtion step is quite
straight forward. Okay, here's an example that I'm going to
walk through. It's the same topology from before.
And I've shown, we're in the initialization phase.
Where you can see, that next to all the nodes, I've written in red, they're costs.
For many nodes, its infinity. For the source node, where we're going to
start from, it's 0. Now, I'll proceed through that while loop.
First step of the wire loop. We're going to take the node with the
lowest distance, that's A, where we want to start from, and do a relaxation around
A. So if A now has cost zero, you can see
I've changed the cost to blue. It's locked in.
It's, once we've visited the node. Then and taken it then we found the path
to that node. The, of course, this is just the source.
Now, I'm going to cull our notes that we visit black and then the relaxation from
here. It looks at the cost of this node at 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 A cost 4 away from a, which has cost 0.
Therefore b's cost could be reached via A cost 4, that's less than infinity.
So, we're going to lower the cost of B from infinity to 4, that's 1 relaxation.
We'll do the same thing for E, E's cost used 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 of cost 10, so E's cost will be 10.
Both of these nodes have been 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 4, just circle B. So we add B to the shortest path 3.
From the source tree from A. Now B would cost 4 as 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 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 2 away from B at Cost 4. So, C can go down to Cost 6, it got lower.
E, while E is a link of Cost 4 away from B, so that can be reached at 8.
E's Cost before used to be 10, so actually E has now been lowered to be cost 8.
So, interestingly, E's distances fall, and not just from infinity down, but it used
to be some finite number 10, now it's gone down to 8.
So we're finding better paths, 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 notes that haven't been visited is c with cost 6.
So we take it. I've changed the cost to blue to say that
it's done. We add this link.
C with cost 6, could be reached at that cost from B.
So we add that to the tree, that's a new link.
I've colored C black too, to indicate that no one's visited.
Now we do our relaxation around C. What's going to happen?
Well H's cost is going to fall. We have the cost of D can be reached 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 as 6.
1 plus 6 is 7, so it's gone 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 are going to find.
Okay. So, continuing, well, it looks like
actually we've done all of the relaxations for c.
So let's continue on. Now, we've gotta pick next lowest node.
There are actually 3 nodes that have costs 7.
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 can be reached at cost 7 from B, so we've now added this link.
Here, to the shortest path G out from A and I've changed the cost of G in 7 to
blue and marked the node G in black. Let's do the relaxation for G.
She has one other neighbor. So that other neighbor, we can reach or a
link across 4, so the cost to reach F by G would be 11.
11 is not bigger than 7, so actually that means that routing to F by G would be a
bad move and we don't lower the cost. And remember that is a new route, so that
hasn't changed anything. Next, moving on, we'll do a relaxation
around F. So first of all we are taking F as the
next lowest node. We're going to add the link but at which F
was reached at cost 7 to the shortest path tree that is a link from B.
It was reached from B at cost 7. We've 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
then 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 it cost in, and seven is now in blue, we've colored the node
black. We've added the link.
E at cost 7 was reached via 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've found the lowest cost way to reach them.
The only node that could potentially change this is this one in red.
7 plus 2 is 9, that's bigger than 8, doesn't change.
Okay, going on. What's left?
D. D, now we'll 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 1 node left, that's H across 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 cost paths to reach 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 typology.
And that's Dijkstra's algorithm. Let me 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 these
optimality property. That for long shortest paths, the smallest
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 that insures once
we've gone out to a certain distance we'll never change our mind later and change any
of the paths we've already selected. >> This hour, we're then going to take a
little run on[UNKNOWN] topology. Actually, the efficiency of, 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 algorithm is going to
grow even more quickly and eventually, for very large networks, the run time will 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 here. And finally, I'll note that it gives us
the complete source tree, or sink tree, depending on which way you run it.
This is actually more than we need for forwarding.
Each node destiny just needs to know the next hop for all particular destinations.
So we have more than we need for forwarding, and we can use it.
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 Dijkstra's algorithm, we can keep moving on and look at the routing
algorithms.