28.2.3. Update Operation in Dijkstra's Algorithm

So, to get to the Bellman-Ford algorithm we have to analyze a little bit more about what is happening in Dijkstra's algorithm. So, in Dijkstra's algorithm whenever we burn a vertices, whenever we visited, we updates all it is neighbors. So, we update the distance of a when we burn a vertices j, we update for every edge j k, we update the distance to k to be what distance we already know for k together with a distance to j and h from j to k.

So, we have a newly discovered distance through j perhaps and we compare it to the distance we already know and we keep the smaller of the Dijkstra's algorithm. So, let us call this operation an update, it updating k from j.

Dijkstra's algorithm works by choosing the next vertex (or node) with the smallest known distance from the source vertex. When a vertex is 'burned,' or finalized, it means its shortest distance is known. The algorithm then updates the distances to its neighboring vertices. For each neighbor, if a shorter path to it is found through the recently burned vertex, the algorithm updates the known shortest distance to that neighbor. This is referred to as the 'update operation.' Essentially, the update checks if the new path (through vertex j) is shorter than the previously known path to vertex k and retains the smaller of the two distances.

Imagine you are trying to find the quickest route from your home to school. Each time you reach a crossroad (or vertex), you think about the roads leading out of that crossroad toward your school. If you find a faster route while standing at that crossroad, you make a note of it. That decision to update your route leads you to consider only the fastest path available at that moment.

So, what we have seen is that in the negative edge weight case, what if we uses the strategy of Dijkstra's algorithm this may not be it is that we will burn a vertices just because it is shortest expected distance among the unburnt vertices does not guarantee that this is correct distances we might find later on a smaller distance. But, in spite of this, this update operation has some useful properties which we can expert.

In graphs with negative edge weights, using Dijkstra's strategy can lead to inaccurate results because simply choosing the vertex with the smallest known distance may not yield the correct shortest path. This is due to the possibility of encountering shorter paths to already 'burned' vertices via newly discovered routes. However, despite this limitation, the update operation in Dijkstra's maintains some safeguards, ensuring that the distances do not go below the actual shortest distance from the source vertex, thus preserving the integrity of distance estimates.

Think of a delivery service that uses a map. If the map indicates a route that minimizes distance but later information reveals a shorter, unconsidered route due to a road being partially blocked or under construction, the service risks delivering late. However, the delivery team keeps track of previous estimates and ensures they won't claim to reach destination faster than what is possible, thereby adjusting to obtain an accurate arrival time.

So, the crucial thing is that we update gives us some upper bound that the distance to k, we already have... So, at any point the invariant that we have is that the value that we have distances to k is greater than or equal to the actual shortest distance from the source to k.

The update operation in Dijkstra's algorithm is crucial because it consistently provides an upper bound for the distances to each vertex during calculations. Initially, if any vertex k has a distance listed as infinity, then it implies that the actual shortest distance to k must be shorter than infinity. Whenever a distance is updated, it is done with the knowledge that the new distance is either the same or shorter than previously known paths, thus creating a reliable estimate at every step.

Imagine you're storing money in a piggy bank. Whenever you want to know how much you have, you remember that you can only have at maximum the amount you've counted, plus anything you've hidden away. Each time you add coins, you make sure your new total is correctly updated without ever claiming to have more than what is realistically possible based on your current collection.

So, if you look at Dijkstra's algorithm then what it does is a particular sequence of greedy updates, it chooses the smallest distance vertex which is not burnt and un burns it and the proof breaks down, because this sequence does not match, necessarily give us a shortest path, if the ways can be negative.

Dijkstra's algorithm employs a greedy approach to update distances, repeatedly selecting the vertex with the smallest distance that has not yet been processed. However, this method can lead to inaccuracies with negative weights, as this greedy choice does not always yield the shortest path. This breakdown occurs because a chosen path may later be misspoken if a negative edge reveals a shorter alternative after the vertex has been finalized.

Think of a traveler who chooses to visit attractions based solely on the highest popularity (or shortest distance). If they rely purely on the popularity ranking, they might miss out on hidden gems that require a small detour but ultimately lead to a better experience. Thus, an initial decision may not account for future revelations or alternate pathways.

--