So, now let us analyze Dijkstra’s algorithm for the single source shortest path problem. Dijkstra's algorithms operate by burning vertices in the analogy we used. We keep track of vertices that have burnt or initially nothing is visited, and initially we do not know any distance to any vertex. We have assumes all distances that at infinity. When we start at the source vertex, let us call it 1 by assumption. So, we set its distance to 0. Then, we repeatedly pick up the first vertex which is not burnt and which has the minimum distance among those which are not burnt, visit, and recompute the distance to all its neighbors.

Before we look at the complexity of these algorithms, we actually first have to verify that it is correct. Dijkstra's algorithms now make these sequences of updates. Its visits vertices in a particular order which is different from breadth-first or depth-first, and we need to justify that this order is actually correct. So, at every point, breadth-first search looks all its neighbors and visits them in the order of their vertex number. Depth-first search will pick the first neighbor, and then explore it further. Dijkstra's algorithm uses the different strategy which is to pick the first, the smallest distance and visited neighbor. We have to justify that this choice which is never under, that is which keeps going forward, and you never go back.

The key to establishing correctness in Dijkstra's algorithm is establishing an invariant. At each iteration, we claim that the burnt vertices are correctly solved. That is at any point if we look at the distances assigned to the vertices that are burnt, then those distances are actually the shortest distance from the source vertex to that burnt vertex. We assume this inductive invariant is true. Now we want to add a new vertex v, such that if we look at the distance to x plus the weight of x v, if this total sum is the smallest among all the vertices which are not burnt.

Now that we have established that Dijkstra's algorithm is correct, let us look at the complexity. There are some obvious loops in this. There is a loop of order n for initializing the visited values to false and distances to infinity. Inside this order n loop, we have two loops: one is to scan the outgoing neighbors, and the other is to choose the minimum vertex, which results in an overall complexity of order n squared.

To get around the bottleneck, we need to maintain the burnt times in a more sophisticated data structure. It turns out, as we need a data structure in which we can quickly find and remove the minimum element, we can use a heap, which allows us to do updates efficiently, and this can reduce the overall complexity to O(n log n).