11.2.1. Finding the Minimum Distance

So, let us go back to Dijskstra's algorithm. In Dijskstra's algorithm, we start with the initial vertex and we keep burning these vertices, right, so we keep visiting vertices according to their distance. So, initially we set the distance to be infinity for everything, right. And we use the starting point as, setting the distance to the start vertex as 0, and then we find the smallest unvisited vertex, set it to be visited and recompute the distance of each of its neighbours, right.

Dijkstra's algorithm is a way to find the shortest path from a starting vertex to all other vertices in a graph. We begin by setting the distance from the starting point to itself as 0. All other vertices initially have an 'infinity' distance, meaning they are unreachable at the start. The algorithm works by continuously exploring the closest unvisited vertex and updating the distances to its neighbouring vertices.

Imagine you're trying to find the quickest route while driving through a city. You start at your home (the starting vertex) and know the travel time to reach the homes of your friends (other vertices). You mark your home as having a travel time of 0 and all other friends' homes as 'unknown' at first. You then take a path through the city, visiting homes based on the shortest travel time you've calculated, updating your estimated travel time to other homes along the way.

So, the bottlenecks were really at this part of the loop. The bottlenecks are first to find the j with the minimum distance.

The main challenge in Dijkstra's algorithm is efficiently finding the unvisited vertex with the smallest distance. Without an efficient method, this could take too long, especially as the number of vertices increases, because we would need to check all distances each time.

Consider looking through a stack of boxes to find the lightest one. If you had no method to quickly identify which box is the lightest, you’d have to lift and weigh each one until you find it. However, if you had a helper providing you with insights or a tool that automatically identifies the lightest box, it would speed up the search significantly.

So, what seems obvious from what we have discussed so far is that we should maintain distance as a heap and use delete min in this case, because we will want a min heap.

To efficiently find the minimum distance in Dijkstra's algorithm, a min heap is used. A min heap allows for quick retrieval of the vertex with the smallest distance. This means that instead of scanning through all unvisited vertices, we can simply extract the minimum value in logarithmic time.

Think of a priority queue, like a line at a coffee shop. The person at the front of the line has the highest priority (the smallest number of customers waiting). When they are served (removed from the heap), the next person in line (the next smallest number) immediately becomes the focus. By arranging itself in a way that always allows the front person to be taken first, waiting time is minimized.

So, recomputing the distance means examining every neighbour k of j. We can use adjacency lists...

When we visit a vertex, we recompute the distances to its neighbours. This involves checking all connected vertices and updating their distances if a shorter path through the current vertex is found. Using adjacency lists makes this process more efficient than using adjacency matrices, as it requires examining only the relevant connections.

Imagine you are recalculating the quickest route to a friend's house after realizing there’s been construction on your usual path. You check which alternate routes are open (neighbours) and see which one gives you the fastest arrival time (shortest distance) by trying out your connections (neighboring paths) instead of retracing the entire city map (matrix) again.

Now, we have not really seen how to update heap values, we have only seen insert and delete min and delete max. So, how does update work?

Updating a value in a heap is crucial for Dijkstra's algorithm. When the distance to a vertex changes, that value must be adjusted in the heap. If you increase the value, you'll need to check upwards (compare it with its parent) to maintain the heap property. Conversely, if you decrease the value, you'll check downwards (compare with children) to ensure the larger values remain positioned correctly.

Imagine you have a stack of books sorted by height. If you get a new book that is taller than a book in the stack, you need to place it back without losing the order. You would lift the new book (increase a value), comparing it against taller books (parent books) until you find the right spot. If instead, you found a shorter book (decrease value), you'd have to see where it now fits among the other books beneath it to ensure everything stays organized.

So, we need this extra information to be kept separately, right. So, we would keep two new arrays pointing from the nodes...

To efficiently navigate between the heap and the original graph, additional data structures (arrays) are necessary to track the indices of vertices in both the heap and the graph. This helps ensure that when we update the heap, we can quickly find the corresponding vertex in the graph and vice versa.

Think of this like a student roster and seating chart for a classroom. If a student moves to a new seat (the vertex moves in the heap), you need to update both the seating chart and the roster. Without this mapping, knowing which students are seated where becomes a tedious process, just like not having a mapping would make updating heaps a complex task.

So, now for instance, supposing we have this previous thing and we want to make this 33 into 9...

By efficiently implementing distance updates and utilizing heaps, Dijkstra’s algorithm runs more efficiently. Each update to the distance takes logarithmic time, allowing the overall complexity to remain manageable even as the number of vertices and edges increases.

Think of a factory assembly line. If each worker has a job that takes a certain amount of time (representing distance) to process a part, optimizing their workflow (using a heap) ensures the fastest output (overall efficiency). Adjusting how tasks are assigned or the order in which they are processed can drastically improve production speed, just as managing the heaps improves Dijkstra's algorithm.

--