So now we have this intuition that at any moment of time,

if we have relaxed all the edges outgoing from some known set of nodes for

which the distances are already known correctly, then the node with the smallest

dist value estimate is also a node for which we know the distance correctly.

So, the main idea of Dijkstra's Algorithm is that we maintain

some set R of vertices for which dist value is already set correctly.

We call this set R, known region.

And initially, we only have node S, the region in the set R,

because for this node, we definitely know that the distance to it is 0.

And then on each iteration, we take the node outside of this region with

a minimum dist value out of all nodes in this outside region, and

we add this node to the known region and relax all the outgoing edges.

And so, after a number of iterations,

which is equal to the number of nodes in the graph,

we will know all the correct distances from origin to all the nodes in the graph.

Let's see how it works in an example.

Here, we have six nodes, some edges, and

the edge weights are written nearby the corresponding edges.

And on top of each node, and under the bottom nodes,

we have the current dist value.

So we start with infinities in all the nodes,

but the origin node to the left, which has dist value of 0.

Now we add this 0 node to the known region, and we now know for

sure that the distance from the origin to it is 0.

And so we color the dist value by green,

because we are sure that this is the correct distance from origin to this node.

And then we color our node in black, and we start processing it.

So we color nodes in black when we start processing them in the same way we did in

the breadth-first search.

Now relax all the outgoing edges from this node.

First relax the edge of length 3, and we improve the dist value from infinity to 3.

And next,

we traverse edge of length 10 to improve the dist value from infinity to 10.

Now what do we know?

We know that the node with a minimum dist value outside of

the known black region is the node with dist value of 3.

So this node actually has a distance of 3, and we color the distance with green and

the node with black, and we start processing this node.

So we process the outgoing edges.

First, edge of length 8, which goes to the node with distance 10, but

new estimate is 3 plus 8, which is 11, which is bigger than 10.

So, nothing changes because of this edge.

And I also have an edge of flag 3, and we improve the dist value from infinity to 6.

And there is also an edge of flag 5,

which improves the dist value from infinity to 8.

And now, what we see is that the node with the minimum dist values,

the node in the top right corner, which has this value of 6.

So we color it with black color and the distance with green and process it.

This edge gives us improvement from infinity to 8.

This edge gives us improvement from 8 to 7,

and this edge gives us an improvement from 10 to 9.

Now the best node is in the bottom to the right and has distance 7.

And it improves the distance estimate for the right most node from 8 to 7,

and notice that there is an edge of weight exactly 0.

This is allowed because 0 is non-negative.

We'll only forbid the edges from being negative, but

non-negative, including 0, is okay.