Because you're maintaining the heap as an essentially perfectly balanced binary

tree, the height of the tree is roughly the log base two of N, where N is the

number of elements in the heap. And because for every operation, you implement

it just by doing a constant amo unt work at each level of the tree, all of these

operations run in O of log N time, where N is the number of items that are being

stored in the heap. As far as the intuitive connection between the heap data

structure and Dijkstra's Algorithm. In the main wild loop of Dijkstra's Algorithm,

we're responsible for finding a minimum, every single iteration. What are heaps

good for? They're good for finding minimums in logarithmic time. That sounds

a lot better than the linear time we're spending in the naive implementation of

Dijkstra's Algorithm. So let's now see how to use heaps to speed up Dijkstra's

shortest path algorithm. Now because every iteration of the wild loop is responsible

for picking an edge, you might expect that we're going to store edges in the heap. So

the first subtle but really good idea is to actually use a heap to store vertices

rather than edges. Going back to the pseudo-code [inaudible] algorithm,

remember that the only reason that we focused on an edge. Well so that we can

then deduce which vertex, namely the head of that edge, to add to our set capital X.

So we're just going to cut to the chase, we're just going to keep vertices not yet

in X and then when we extract them in from the heap, it'll tell us which is the next

vertex to add into the set capital X. So the picture we're going to wanna have in

mind is Dijkstra's choice path algorithm at some intermediate iteration. So

there'll be a bunch of vertices in the, the set capital X source vertex plus a

bunch of other stuff that we've sucked into the set so far. And then there'll be

all the vertices we haven't processed yet. A big group V minus X. Then there's gonna

be edges crossing this cut in both directions from X to V minus X and vice

versa. Now before I explain the second invariant, let's just recall what the

straightforward implementation of Dijkstra's Algorithm needs to do. What it would do is

search through all the edges and it would look for any eligible edges. Those with

tail and X, and head and V minus X. So in this picture, there w ould be three such

edges. I've drawn the example so that two of the edges, the top two edges, both

share a common head vertex whereas the third edge has its own head vertex. The

straightforward of limitation of Dysktra's Algorithm we?d compute Dystra's greedy

score for each of these three edges And remember, by definition, that's the

previously computed shortest path distance to the tail of the arc V, plus the length

of the arc VW. So the straightforward implementation just computes this. In this

case, it would compute it for three edges. And whichever the three edges won had the

smallest score. The head of that edge would be the next vertex that gets added

to X. So let me specify the second invariant, and then I'll tell you how to

think about it. So, because we're storing vertices rather than edges in the heap,

we're going to have to be fairly clever with the way we define the key of a vertex

that's in this heap. [sound] So we're going to maintain the property that the

key of a vertex V is the smallest greedy Dijkstra score of any ver, any edge which

has that vertex as its head. So let me show you what I mean in terms of our

example, where we have three crossing edges. Suppose for these three edges in

the upper right that happen to have of Dijkstra [inaudible] scores of seven,

three, and five. Let's look at what the key should be for each of these three

vertices I've drawn in V minus X. Now for the timeline vertex this is pretty

interesting. There are two different edges whose tail is in X, and have this vertex

as their head. So what should the key of this vertex be? Well, it should be the

smallest Dijkstra greedy score of any of the edges whose tail lies on the left-hand

side that terminate at this vertex. So there's two candidate edges. One has

Dijkstra greedy score three. One has Dijkstra greedy score seven. So the key

value should be three, the smaller of those two. Now, the second vertex, there's

only a single edge that has tail in X and that terminates at this vertex. So the key

for this vertex should jus t be the score at that weak edge. So in this case that's

gonna be five. And then this poor third vertex, there's actually no edges at all,

that, started X and terminated at this vertex. There's only one arc going the

wrong direction. So for any edge, sorry, for any vertex outside of X that doesn't

have any eligible edges terminating at it, we think of the key as being plus

infinity. So the way I recommend thinking about these heap keys is that we've taken

what used to be one round tournament, winner takes all And we've turned it into

a two round knockout tournament. So in our straightforward implementation of

Dijkstra's algorithm, we did a single linear search through all the edges, and

we just computed the [inaudible] Dijkstra's score for each and we picked

the best. So in this example we would have discovered these three edges in some

order. Their scores are three, five, and seven. And we would have remembered the

edge with score three as being the best. That would have been our winner of this

winner take all tournament. Now when we use the heap, it, we're factoring it into

two rounds. So first, each vertex in V minus X runs a local tournament. To elect

a local winner, so each of these vertices in V minus X. Says, well let me look at

all of the edges. For whom I'm the head and also the tail of that edge is in X.

And amongst all of those edges that start in X and terminate at me, I'm going to

remember the best of those. So that's the winners of the local tournament of the

first round. And now the heap is only going to remember this set of first round

winners. Right, there's no point in remembering the existence of edges who

aren't even the smallest score that terminate at a given vertex, because we

only care about the smallest score overall. Now when you extract min from the

heap, that's in effect. Executing the second and final round of this knockout

tournament. So each of the vertices of V minus X has proposed their local winner.

And then the heat in an extract min just chooses the best of all of those local

winners. So that's the final proposed vertex that comes out of the heap. So the

point is that if we can successfully maintain these two invariants, then, when

we extract min from this heap, we'll get exactly the correct vertex, W star, that

we're supposed to add to the set capital X next. That is, the heap will just hand to

us on a silver platter exactly the same choice of vertex that our previous

exhaustive search through the edges would've computed. The exhaustive search

was just computing the minimum in a brute force way, in a single winner take all

tournament. The heap implemented in this way chooses exactly the same winner. It

just does it in this 2-round process. Now, in Dijkstra's algorithm, we weren't

supposed to merely just find the vertex W star to add to X. We also had to compute

its shortest path distance. But remember, we computed the shortest path distance as

simply the Dijkstra greedy score. And here the Dijkstra greedy score is just going to

be the key for this heap that's immediate from invariant number two. So we're using

the fact here that our keys are, by definition, just. The smallest greedy

scores are edges that stick into that vertex W STAR so again exactly

replicating. The computation that we would have done in the straightforward

implementation, just in a much slicker way. Okay? But we're adding exactly the

same vortices, in exactly the same order, and we're computing exactly the same

shortest path distances in this heap of notation, provided of course that we do

successfully maintain these two invariants throughout the course of the algorithm. So

that is now what I owe you. We have to pay the piper. We've shown that if we can have

a data structure with these properties. Then we can simulate the straight forward

implementation now I have to show you how we maintain these invariants without doing

too much work. All right. So maintaining invariant number one will really take care

of itself. Really sort of by definition the vertices which remain in the heap are

those that we haven't process ed yet, and those are the ones that are outside of

capital X. So really the trick is, how do we maintain invariant number two? Now

before I explain this let me point out, that this is a tricky problem. There is

something subtle going on. So as usual, I want you to think about this shortest path

algorithm at some intermediate iteration. Okay? So take a, take a snapshot. A bunch

of vortices have already been added to X. A bunch of vortices are still hanging out

in the heap. They haven't been added to X. There's some frontier, there's a, just

crossing, possibly in both directions. And suppose at the end of a current iteration

we identify the vortex W, which we're going to extract from the heap and

conceptually add to the set X. Now the reason things complicated is when we move

a vortex from outside X to inside X. The frontier between X and V minus X changes.

So in this picture, the old black X becomes this new blue X. And what's really

interesting about the frontier changing is that then the edges which cross the

frontier change. Now, there might be, there are some edges which used to cross

the frontier and now don't. Those are the ones that are coming into W. Those we're

not so concerned with. Those don't really play any role. What makes things tricky is

that there are edges which used to not be crossing the frontier but now they are

crossing the frontier. And those are precisely the edges sticking out of W. So

in this picture there are three such edges which I will highlight here in pink. To

see why it's tricky when new edges all the sudden are crossing a frontier let's

remember what invariant number two says. It says that for every vertex which is

still in the heap, which is not yet in X, the key for that vertex better be The

smallest Dijkstra Grady score of any edge which comes from capital X and sticks into

this vertex of V. Now in moving one vertex into X, namely this vertex W, now there

can be new edges sticking into vertices which were still on the heap. As a result,

the appropriate key value for vertices i n the heap might be smaller. Now the W has

been moved into X. And the candidates for the vertices in the heap whose keys might

have dropped are precisely those vertices on the other end of edges sticking out of

W. So summarizing, the fact that we'd added a new vertex to capital X and

extracting something from the heap, it's potentially increased the number of

crossing edges across the frontier, because the frontier has changed. And

therefore, for vertices that remain in the heap, the smallest greedy score of an edge

that sticks into them from the set X might have dropped. So we need to update those

keys to maintain invariant number two. Now, that's the hard part. Here's what we

have going for us. We've damaged the keys perhaps by changing the frontier, but the

damage is local. We can understand exactly whose keys might have dropped, so as

suggested by the picture, the vertices whose keys we need to update are precisely

those at the head of edges that stick out of W. So for each outgoing edge from W,

the vertex we just extracted from the heap, we need to go to the other end of

the edge and check if that vertex needs its key to be decreased. So here's the

pseudo code to do this. So when we extract the vertex W from the heap, that is when

we conceptually add a new vertex W. To the set X, thereby changing the frontier, we

say, well, you know, we know the only vertices that might have to have their key

changed, they're the ones on the other side of these outgoing arcs from W. So we

just have a simple iteration over the outgoing edges, W V, from the vertex V.

Now I haven't shown you any edges in the picture like this, but there might well be

some edges where the head of the arc V is also in the set X, is also already been

processes. But anything in X is not in the heap. Remember, the heap is only the stuff

outside of X. So we could care less about the stuff outside. Of the heat, for not

maintaining their keys. So we do an extra check. If the head of this edge is in fact

still in the heap, that is if it's not in X So i n the picture, for example, this

would be true for all three of the vertices that are on the other end of arcs

pointing out of W. And for each of these vertices V, we update its key. And the way

we're going to update its key is, we're just going to rip this vertex out of the

heap. We're going to recompute its key and constant time, and then we're going to

reinsert it into the heap. And since all heap operations take logarithmic time,

this key update will be logarithmic time. As an additional optimization, I wanna

point out that if one of these vertices V's key does change, it can only change in

one way. So remember, what is the key? The key is the smallest Grady Dijkstra score

of all of the edges that start next and stick into this vertex. So that's the

local tournament or the first round tournament happening at this vertex V. Now

the only thing which has changed. Before and after we added this vertex, W to X, is

that now one new edge is sticking into this vertex, V. All of the old edges

sticking into it from X are still sticking into it, and now there's one extra

candidate in its local tournament, namely this edge, WV. So either WV is the local

winner; either it has the smallest Dyxtra-Greedy score of them all. That

terminated this vertex, or it doesn't, in which case the previous winner is still

the new winner. So if that is, the new key value can only be one of two things.

Either it's the old key value--that's the case where this. Extra entrance, the edge

from W to V is irrelevant. Or, if it's changed, it has to have changed to the

[inaudible] score of this edge, W-V. And the formula for that is the shortest path

distance. That we just computed for W where W has been processed at this point

plus the link of the direct arch from W M V. And again conceptually this formula is

just a greedy Dijkstra score for the arc WV. The new entrance in V's local first

round tournament. So now, having updated V's key appropriately, so that invariant

#two is restored. And once again, the key of every vertex does reflect the sma llest

greedy, Dijkstra greedy score of any edge sticking into it from the set X. We can

safely reinsert this node back into the heap with its new key value. And these

three lines together are just a key update in logarithmic time, for one of these

vertices that's at the other end of an arc sticking out of the vertex W. So let's

tally up the running time in this new implementation. One thing I want you to

check, and this will definitely help you understand this refined implementation of

Dijkstra's algorithm, is that essentially all the work done is through the heap API.

That is, all of the running time that we have to account for is in heap operations.

We don't really do nontrivial work outside of heap operations. And again recall that

the running time of any heap operation is logarithmic in the number of elements in

the heap. Our heap is storing vertices. It's never gonna have more than N things

in it. So the running time of every heap operation is big O of log N. So what are

the heap operations that we do. Well, we extract men and we do it once per

iteration of the wild loop. So there's N minus one iterations of the wild loop,

just like before, but now instead of doing an exhaustive search through the edges, we

just do a simple extract men from the heap and it gives us on a silver platter the

vortex we should add next. So what do we do beside extract mins? Well, we have to

do this work paying the piper. We have to maintain invariant #two. And every time we

extract a min, that then triggers some subsequent key updates. And remember, each

of these key updates is a deletion of an element, from the heap followed by an

insertion. So how many deletions and insertions do we do? Well, at first this

might seem a little bit scary. Right? Because we do a roughly linear number of

extract mins. And a vertex might have as many as N-1 outgoing arcs. So it seems

like a vertex could trigger as many as N-1 key updates, which is theta of N

[inaudible] operations. And if we sum that up over the N iterations of the wild loop

that w ould give us N squared heap operations. So, and indeed, in dense

graphs, that can be the case. It is true that a single vertex might trigger a

linear in N [inaudible] number of [inaudible] operations. But that's the

wrong way to think about it. Rather than have this vertex-centric perspective on

what, who's responsible for heap operations, let's have an edge-centric

view. So for each edge at the graph, let's think about when can this be responsible

for some heap operations, in particular a decrease in key in the resulting insertion

and deletion. If you have an edge and it points from the vertex V to the vertex W.

There's actually only one situation in which this edge is going to be responsible

for a, a decrease in key. And that's in the case where the tail of the edge, V.

Gets sucked into the set X before the head W of this edge gets sucked into the set X.

If that happens, if V gets sucked into X and W is still outside of X, then indeed

we're gonna have to decrease the key of W, just like we did in the examples. But

that's all that's gonna happen: V can only get sucked into X once and never gonna

leave it. So it's only responsible for this single decrease in key of its head W.

And that's one insertion and one deletion. And in fact, if the endpoints of this edge

get sucked into X in the opposite order, if the tail of, excuse me, if the head of

this edge W gets sucked into X first. That doesn't even trigger a, a key decrease for

V, and V will never have its de key decreased, because of this particular arc,

from V to W. So the upshot is that each edge VW of the graph triggers at most one

insert delete combo. So what does this mean, this means that the number of heap

operations. Is big O of N, that's for the extract mins. Plus big O of M. That's for

the insert the leak combos triggered by edges during the decreased keys. Now just

to, I'm gonna write this in a, in a simplified way. This is just O of M, the

number of edges. And this is because of our assumption that's there's a path to s

from every other vertex. If yo u think about it that means that the graph is at

least weakly connected if you picked it up it would stay together in one piece. So

that means it at least contains a tree, at least an in an undirected sense, which

means it contains at least N minus one edges. So we're in the case of weakly

connected graphs where N dominates M. M is always as big as N at least up to a plus

one. So what that means is the running time of Dijkstra's algorithm, with this

heap implementation, is just a log factor larger. Remember, every heap operation

takes time logarithmic. So we do a linear in M number of operations; each takes time

logarithmic in N. So the running time is M log N. With, I should say, quite good

consistence. So this is a really, really impressively fast algorithm, for computer

such a useful problem as shortest paths. So we got a little bit spoiled in our

discussion of graph searching connectivity, where it seemed any problem

we cared about we could solve in linear time, over M plus N. So here we're picking

up this extra logarithmic factor, but I mean, come on, this is still awesome. A

running time of M log N is unbelievably faster than a running time of M times N,

which is what we had in the straightforward implementation. So this

deft use of the heap data structure has given us a truly blazingly fast algorithm

for an extremely well motivated problem, computing shortest paths.