27.1.2. Prof. Madhavan Mukund

So, now let us analyze Dijkstra’s algorithm for the single source shortest path problem. Dijkstra's algorithms operate by burning vertices, where we keep track of vertices which have burnt. Initially, nothing is visited, and we assume all distances are at infinity. When we start at the source vertex (let's call it 1), we set its distance to 0. Then, we repeatedly pick the first vertex which is not burnt and has the minimum distance among those that are unburnt, visited, and recompute the distance to all its neighbors.

Dijkstra's algorithm is designed to find the shortest paths from a starting vertex to all other vertices in a weighted graph. Initially, all vertices are considered unvisited, and the distance to the source vertex is set to zero, while all others are treated as infinitely far away. The algorithm then explores the nearest unvisited vertex, updates the distances to its neighbors based on the weight of the edges connecting them, and marks the vertex as 'burnt' or visited. This process continues until all vertices are visited.

Imagine you are a postal worker trying to deliver mail in a city. You start from a central post office (the source vertex) and want to find the shortest route to all neighborhoods (other vertices in your graph). Initially, you know the distance to the post office is zero, but you have no idea about other neighborhoods. You check which neighborhood is closest and map a route to it, updating your map of distances as you go. This method ensures you always take the shortest paths available.

Before we look at the complexity of these algorithms, we actually first have to verify that it is correct. The key to establishing correctness involves an invariant: at each iteration, the burnt vertices are correctly solved. The claim is that if we add a new burnt vertex 'v', then the distance to 'v' cannot be smaller than what we have computed thus far.

To ensure Dijkstra's algorithm is correct, we utilize a principle known as an invariant. This states that at every stage of the algorithm, the distances to the vertices that have already been visited (or burnt) are the shortest possible from the source. When we select a new vertex 'v' to visit next, we know its distance must be accurate, as it has been determined based on the shortest paths to its predecessors and their edge weights. As such, once a vertex is visited, its distance cannot be improved later by choosing a different vertex.

Consider a race car driver who can only see which cars are ahead during laps. After completing a lap (visiting a vertex), they note the fastest time recorded for that lap (the shortest distance). Once a lap has been finished, the driver cannot retroactively say they would have raced faster if they had chosen a different path because they’ve already completed the circuit and have good data on their speed.

After establishing correctness, we look at the complexity. Dijkstra's algorithm has a significant number of operations, including loops to initialize distances and loops to check neighbors. Initially, it operates in O(n^2) time complexity due to finding the minimum vertex and scanning its neighbors. This can be improved using a more sophisticated data structure such as a heap, which will allow operations to be carried out in O(log n) time.

The performance of Dijkstra's algorithm in its simplest form is O(n^2) because for each vertex (n), it contains loops that scan the entire vertex list (hence the quadratic term). However, when using a priority queue (like a heap), we can optimize the algorithm. The heaps facilitate finding the minimum distance vertex and updating vertices in logarithmic time, leading to an optimized complexity of O(n + m log n) where 'm' is the number of edges.

Think of a line of cars at a traffic light: if each driver looks for the shortest route while stuck in traffic (O(n^2) method), it takes a long time. If the drivers had a navigation system that could quickly compute the best paths in real-time (using a heap), they would get to their destinations much faster and more efficiently.

Dijkstra's algorithm makes a crucial assumption that there are no negative edge costs. If the graph features negative cycles, the algorithm might mislead by suggesting shorter paths when, in fact, they might not exist. Therefore, while negative edges can be present, the important condition is that no negative cycles should exist in the graph.

Dijkstra's algorithm is built on the premise that shorter paths do not appear as we traverse and add vertices. Introducing negative cycles can cause the algorithm to return incorrect results, suggesting a path that could lead to an infinite decrease in distance, thus making the concept of 'shortest path' meaningless. If negative edges exist without negative cycles, alternative algorithms like Bellman-Ford can be used.

Imagine a treasure hunt where some paths can lead to negative experiences (like taking a longer, more difficult road). If you can go back through those paths repeatedly, each trip becomes cheaper, creating an illusion of an infinitely short path, which is akin to negative cycles. However, if those paths are just long without the repeating chance, you can calculate your route successfully with Dijkstra's method.

--