27.2.2. Complexity Analysis

So, now let us analyze Dijkstra’s algorithm for the single source shortest path problem. Recall that Dijkstra's algorithms operate by burning vertices in the analogy we used. We keep track of vertices which have burnt... initially we do not know any distance to any vertex. So, we have assumed 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.

Dijkstra's algorithm is used to find the shortest paths from a single source vertex to all other vertices in a weighted graph. It begins by treating all distances to vertices as infinity (unknown), except for the starting vertex, which is assigned a distance of zero. This establishes the starting point to build from. The algorithm uses a 'burning' analogy where it processes vertices in order of their shortest known distance from the source, marking them as 'burnt' once processed.

Think of Dijkstra's algorithm like a fire spreading out from a campfire (the source vertex). At first, the warmth (or distance) is only felt at the campfire, and as the fire spreads out, it burns through the nearby brush (vertices) that are closest first. The farther away brush may take longer to catch fire, symbolizing that they are farther from the shortest path.

Before we look at the complexity of these algorithms, we actually first have to verify that it is correct. The key to establishing correctness in this particular case is which establishes what is called an invariant.... So, the claim is that if we now add this to our burnt set, right so we extended our burnt set like this by include v, then, the distance of v cannot be actually smaller than what we have computed now and we could not change it at later update.

The correctness of Dijkstra's algorithm hinges on establishing an invariant: that the distances assigned to burnt vertices represent the shortest paths from the source vertex to those vertices. The algorithm ensures that once a vertex is marked burnt, its shortest distance is finalized. When processing a new vertex, the algorithm always selects the one with the smallest computed distance that hasn't been burnt yet, which guarantees the optimal choice based on the distances thus far.

Imagine you are in a maze trying to find the exit and marking paths you have traveled (burnt vertices). Once you confirm a path as the shortest to a certain point, you know that any future paths to that point can’t be shorter. Each time you reach a new section of the maze, you only consider paths that lead to the shortest previously noted sections.

So, now having established that it is correct, let us look at the complexity. There are some obvious loops in this... In each iteration, we burnt a vertex. This requires an order n scan to find the minimum vertex to burn.

The complexity of Dijkstra's algorithm depends on how the graph is represented. If using an adjacency matrix, the time complexity for finding the minimum vertex and updating neighboring vertices can lead to an overall complexity of O(n²). However, switching to an adjacency list can improve efficiency, since each vertex's neighbors are stored in a concise manner, reducing the time needed to traverse edges. To further improve efficiency, more advanced data structures, like heaps, can ensure that selecting and updating vertices is done in logarithmic time.

This can be likened to a network (like a city road map). If roads (edges) are listed individually (adjacency list), finding alternate routes becomes quicker compared to a larger grid that lists every intersection in a square (adjacency matrix), making it less efficient to search for the shortest route.

Dijkstra algorithm makes a very crucial assumption which underlies the correctness of its greedy step... If I have negative cycles in a graph, the question of the shortest path does not even make a sense.

Dijkstra's algorithm assumes there are no negative-weight edges because the presence of such edges can lead to situations where a previously 'burnt' vertex could be revisited with a shorter path, thus violating the algorithm's foundational logic. Negative cycles create conditions under which the 'shortest path' becomes ambiguous or undefined, as the cost can be reduced indefinitely by traversing the cycle repeatedly.

Consider a taxi route where a driver can pick up and drop off passengers, but routes might incur costs (negative weights) for returning empty. If the driver repeatedly loops through a route with passengers (positive edges), they earn money, but if they keep returning empty (negative edges), their overall profit can fluctuate unpredictably, making the determination of the shortest path financially ambiguous and impractical.

--