11.3.1. Time Complexity of Dijkstra's Algorithm

In Dijkstra's algorithm, we start with the initial vertex and we keep visiting vertices according to their distance. Initially, we set the distance to infinity for all vertices except the starting point which is set to 0. We then find the smallest unvisited vertex, mark it as visited, and recompute the distance of each of its neighbors.

Dijkstra's algorithm is a way to find the shortest path from a starting point to all other points (or vertices) in a graph. It begins by assuming all distances to other vertices are infinity, meaning they are unreachable at the start. The starting vertex has a distance of 0 because it takes no cost to reach itself. The algorithm repeatedly identifies the unvisited vertex with the smallest distance, marks it as visited, and updates the distances of its neighboring vertices based on the shortest paths found so far.

Think of a map where you are trying to find the shortest route to deliver packages. You start at your location (the starting vertex) with no distance. As you evaluate routes (neighbors), you adjust your understanding of how far each destination is (distance) based on what you discover. The process continues until you've determined the best path to each location.

The bottlenecks in Dijkstra's algorithm occur first in finding the vertex with the minimum distance, which can take O(n) time in a naive implementation. To optimize this, we can maintain the distances in a min-heap, allowing us to delete the minimum in logarithmic time.

One of the challenges (or bottlenecks) in Dijkstra's algorithm is efficiently finding the vertex with the smallest distance among unvisited vertices. If implemented naively, this requires scanning through all unvisited vertices, which takes linear time (O(n)). To overcome this, we can use a min-heap data structure which allows us to quickly retrieve and remove the vertex with the smallest distance in logarithmic time (O(log n)). This optimization significantly speeds up the algorithm.

Imagine you are a librarian trying to find the book with the least number of pages (minimum). If all the books are just piled on a table, you need to check each one, which takes a long time. Instead, if you organize them on a shelf by page count, finding the book with the least pages becomes much quicker—like using a priority list (min-heap) instead of a random pile.

When recomputing distances, we also need to update values in the heap. If we increase a value, we fix violations upwards, and if we decrease a value, we fix violations downwards in the heap.

When updating the distances of vertices in the min-heap, there are two scenarios: increasing the distance or decreasing it. If we increase a distance, this may violate the heap property because the value can become larger than its parent, so we need to 'fix' this by moving the value upwards in the heap. Conversely, if we decrease a distance, we check the children of the node and potentially move the value downwards to maintain the heap property.

Imagine a queue in a supermarket—if someone decides to leave the queue and moves before a person ahead of them, the queue needs to adjust. Similarly, in a min-heap, if a value increases, it needs to move up like a person moving ahead in line, while if it decreases, it might need to move down, like a latecomer joining the back of the line.

To efficiently locate vertices in the heap, we keep additional mapping information in two separate arrays that link graph nodes with heap indices and vice versa.

In Dijkstra's algorithm, as we update distances, we need to know where each vertex is located inside the heap. To do this efficiently, we maintain two arrays: one that maps each vertex to its index in the heap and another that does the reverse. This allows constant time access to locate any vertex within the heap, enabling rapid updates without needing to search the heap entirely.

Consider a library system with a catalog: each book has a shelf location mapped in a database. When you want to find a book (vertex), you can quickly look it up in the catalog (array), retrieve its shelf number (heap index), and access it without searching the entire library. This makes finding and updating information very fast.

The overall time complexity of Dijkstra's algorithm using a heap is O((n + m) log n), where n is the number of vertices and m is the number of edges.

Using a min-heap with adjacency lists allows Dijkstra’s algorithm to run efficiently. The time complexity can be broken down: finding the minimum distance vertex takes O(log n) time and needs to be done up to n times (once for each vertex), while updating distances takes O(log n) for each edge (up to m edges). Thus, the total complexity comes out to O((n + m) log n).

Think of a delivery service that has to compute the fastest routes to multiple locations (vertices) based on various streets (edges). With a good system in place, you can quickly update routes and times, ensuring you’re not wasting time finding the shortest paths. The efficiency of the overall process is mirrored in the complexity analysis of Dijkstra's algorithm.

--