11.2. Dijkstra's Algorithm

In Dijkstra's algorithm, we start with the initial vertex and we keep burning these vertices. We keep visiting vertices according to their distance. Initially, we set the distance to be infinity for everything, and the distance to the start vertex is set to 0. Then we find the smallest unvisited vertex and set it as visited, recomputing the distance of each of its neighbours.

Dijkstra's algorithm is a method for finding the shortest path from a starting vertex to all other vertices in a weighted graph. At the beginning, the algorithm sets the distance from the starting vertex to itself as zero (since there's no cost to stay at the starting point) and every other vertex's distance is set to infinity (meaning they are unreachable at the start). The algorithm then repeatedly selects the vertex with the smallest known distance, marks it as visited, and updates the distances to its neighbouring vertices based on the current vertex's distance. This process continues until all reachable vertices have been visited.

Imagine you're planning to drive from your home to several destinations in a city. You start at home, marking the distance to your home as zero because you are already there. For every other place (like the mall, a friend's house, etc.), you initially think you can't reach them, so you mark their distances as infinity. Each time you find the shortest drive to a destination, you mark that destination as visited and then calculate the possible shorter paths to other places based on what you just learned.

The bottlenecks are first to find the vertex with the minimum distance, which could take order n time if we scan all the unvisited vertices. We should maintain the distances as a heap and perform delete min operations to optimize this process.

Finding the vertex with the minimum distance among unvisited vertices can slow down the algorithm if done naively. This is because it could require checking every unvisited vertex (O(n) time). Instead, using a min-heap data structure allows for more efficient retrieval of the minimum vertex. In a min-heap, the smallest element can be accessed quickly, typically in logarithmic time, which significantly reduces the computational time as the number of vertices increases.

Think of it like searching for the fastest route to your favorite restaurant from your home among several options. If you simply list all routes and check their distances one by one, it would take a long time, especially if there are many routes. However, if you have a GPS system that can quickly tell you which route is the shortest in real-time, you'll get to your restaurant much faster!

Recomputing distances means examining every neighbour of the selected vertex. To do this efficiently, we can use adjacency lists instead of an adjacency matrix.

Once a vertex is marked as visited, the algorithm needs to consider the distances to its directly connected neighbours. If we're using an adjacency list, which lists all neighbours for each vertex, it means we can quickly access only the relevant vertices without scanning a full matrix that encompasses all possible connections. This leads to much faster updates to the distances.

Imagine you are making plans with friends in a city where the streets are like an adjacency list. If you want to check how to get to the nearest coffee shop, you don't get bogged down looking at the entire city map. Instead, you only check the nearby shops, making it much faster to find the best route to each place without unnecessary detours.

To update a heap, we can either increase or decrease the value of a node. If we increase a value, we fix violations upwards; if we decrease a value, we fix violations downwards.

When the distance to a vertex changes because of a new path found, it might require us to adjust its position inside the heap. If we decrease the distance, the node might now be smaller than its parent, necessitating a downward fix (moving it down in the heap). Conversely, if we increase the distance, it may become larger than its parent, necessitating upward fixes. These adjustments ensure that the heap maintains its properties, allowing the algorithm to function correctly.

This can be likened to rearranging a list of tasks based on their priority. If a task (like finishing a report) has its deadline sped up (making it a higher priority), it might need to be moved up the list or even at the top. But if the deadline is pushed back (making it less urgent), you might move it down your to-do list. To keep your tasks organized and manageable, you have to adjust their positions based on their changing priorities.

To efficiently update the distance in the heap, we need additional arrays to keep track of where each vertex is located in the heap.

When a vertex's distance is updated, we need to know its precise location within the heap to perform the necessary modifications efficiently. By maintaining two arrays—one that maps vertices to their heap locations and another that maps heap indices back to their vertices—this can be done quickly. This additional structure allows for quick access and updates without having to conduct a full search through the heap.

Think of it like a library system where books are arranged in a specific order on the shelves. If you have a database that tells you exactly where each book is located, then finding or re-shelving a book is much faster. Instead of checking every shelf for a book, you can simply look it up in the database and go directly to its location.

Using the heap with these updates allows us to find the minimum vertex in log n time and update the distances in m log n time overall.

By combining the min-heap structure with efficient distance updates, Dijkstra's algorithm optimizes the process. Each time we need to get the smallest vertex, we can do so in logarithmic time due to the properties of heaps. Additionally, updating distances based on edges (or connections) can be managed in a similar fashion. This results in an overall time complexity of O(n log n) due to the repeated operations required for n vertices in a graph.

Imagine now you're not just looking for a single best route in the city but a whole set of best routes as you plan a trip across several destinations. Each time you plan a new leg of your trip, the optimizations you make (in how quickly you find the next best route and adjust your plans based on traffic or construction) drastically improve the overall time it takes to finalize your itinerary. That’s what Dijkstra’s optimization achieves for navigating a graph!

--