Here's a demo of Dijsktra's algorithm running in a large digraph.

So the source is the protects the center with the open circle and you can see it

considers the vertices in the graph in order of their distance from the source.

Now you can see this is maybe like a lake in the middle of the graph,

And so it's not going to move on from those vertices.

It's going to take a little while to get around the lake.

And again, if, this visualization is produced by our code,

Then it, and it gives a very, natural feeling for the way that the algorithm

works, This, in principle. And I think, in fact,

in many cases, is what your, car does when you turn the map system on,

It computes the shortest path to everywhere,

And then it's all ready when you ask for a certain place, how to get there.

So here's just, starting from another point in the graph.

You have, if you happen to live at a corner of the Earth, then it's going to be

slightly longer to get to the other corner.

And, a nice feeling for how the algorithm gets its job done.

Again, when it gets into those blank areas, it takes a little while to get over

to the other side. And of course if we had islands, if we had

little roads in the middle there that were not connected,

Then we know where to get to them from the source and we wouldn't see them.

And that's fine for the way our algorithm works.

We just leave that out of the demo and the proof to avoid adding an extra comment

about that for every algorithm. That's a visualization of Dijkstra's

algorithm on a large graph. So, so how do we prove it's correct?

Well, essentially we've prove that it's an instance of the generic algorithm.

So, first thing is that every edge is relaxed exactly once.

Every time we, everytime we put a vertex onto the tree, we relax all the edges that

come from that vertex and we never reconsider the vertex.

And what does relaxation do? Relaxation ensures that after the

relaxation, either way there was before, afterwards, you have the distance to w is

less than or equal the distance to v plus e to the, e plus the way to the edge.

Either it's equal cuz we just made it that way, or it's less than it was before and

the edge was not relevant. And this inequality is going to hold for

every an, entry for every edge corresponding to every edge, for just two

entries corresponding to every edge because number one, the, these two values

are always increasing. We never I'm sorry, we're always

decreasing. The only thing we ever change, only reason

we ever change distTo w is to make it smaller.

If we, if we found an edge that would make it bigger we ignor that edge,

So it's always decreasing. So when we change distTo w, we're not

going to make that inequality holds. We're just going to make it better.

And this distTo v is not going to change at all.

Once we relax an edge from a vertex, we're done with that vertex.

We're not going to process that at all. So, then when we're done we have the

optimality conditions hold that exactly is the optimality condition.

And, not only that, we have a path from the source to every vertex.

So that's the correctness proof for Dijkstra's algorithm based on the

optimality conditions. Here's the code.

It's similar to code that we've seen before.

We're going to use the indexed priority queue that allows us to implement the

decreased key operation. And we have our edgeTo and distTo arrays

that are part of the shortest paths computation and the goal of the shortest

paths computation. So we initialized the constructor,

initializes those rays and including the Index

Minimum PQ. and we start out with all the distances infinity except for the distance

of the source is zero. We put the source on the priority Q and

then what we're going to do is take the, Edge that closest to the source off the

priority. That's on the priority queue off and then

relax all the edges that are adjacent to that, so I'm using our standard iterator

to get all the edges that emanate from that vertex and relax them. And then the

relax code is just like the code that was showed when describing relaxation, except

that it also updates the priority queue. If the, vertex, that, that edge goes to is

on the priority queue, it gives a new shorter way to get to that,

So we have to, decrease the key on the priority queue,

Cuz if it's not on the priority queue, we insert it,

And that's it. That's a complete implementation, of

Dijsktra's algorithm using modern data structures.

Now, this algorithm might seem very familiar than, if you've been paying

attention. It's essentially the same algorithm as

Prim's algorithm. The difference is that, in both cases,

we're building what's called a spanning tree of the graph.

But in Prim's algorithm, we take a vertex that, that's not on the tree using the

rule of let's take the vertex that's closest to the tree, anywhere on the tree,

Closest to some vertex on the tree. For Dijsktra's algorithm, we take next,

the vertex that's closest to the source through a path, they go through a tree and

then into a non-tree vertex. That's the difference and the differences

in the code have to do with the fact that Prim's algorithm is for an undirected

graph, Dijsktra's algorithm is for a directed graph,

But essentially, they're the same algorithm.

And actually, several of the algorithms that we've talked about are in this same

family. They compute a spanning tree.

I have, you, you have a tree that takes care of where that records where you've

been in the graph, From every vertex, back to where you

started. Then you used different rules for choosing

which vertex to add next. For breadth-first search, you use a Q, for

depth-first search, you use something like a stack and then you have to decide what

to do, if you encounter a vertex that you've been to before.

But many graph algorithms use this same basic idea.

So in particular, when we are talking about what the running time of Dijsktra's

algorithm, it depends on what priority Q the implementation we use,

And it's the same considerations as for Prim's algorithm.

We have V insert operations, every vertex goes on to the priority queue. V

delete-min, every vertex comes off the priority queue. and for every edge, in the

worst case, we could compute decrease-key operation.

So, the original implementations of Dijsktra's algorithm used an unordered

array, Which would mean that it would take time

proportional to V to find the minimum, To find the vertex closest to the source.