28.2.2. Properties of Shortest Paths

Now, what we know is that this is a loop and since it is a loop, the weight is greater than or equal to 0, it cannot be negative, because we have ruled out negative loops. So therefore, if I take this path and I just cut out this loop, then I have a direct path from s to t. And if I look at the cost of the direct path from s to t, it cannot be any bigger than this one, because at best this loop has 0 and decrease nothing but, in the general case the loop has some positive cost and actually reduce the cost. So, shortest path never loops, so it will never does not sent vertex twice, this means that I at most have at most n minus 1 edges.

The shortest path between two vertices in a graph will never visit the same vertex more than once, effectively meaning that it does not contain loops. If there is a loop, the cost associated with it is at least zero (since we have ruled out negative loops), so removing the loop from the path will either keep the cost the same or decrease it. Thus, the shortest path will consist of no more than n-1 edges, where n is the number of vertices in the graph.

Imagine traveling from one city to another without visiting the same city twice on the way. If you took a detour that involved going back to a city you just left, you would only increase your travel time instead of finding a quicker route. Hence, the shortest path is simply the most direct route that doesn’t re-visit any cities.

The other property is that regardless of how the shortest path looks, along the way every path that makes up the shortest path is itself the shortest path. So, for instance I have a path like this from s to t which goes through some intermediate vertices v1, v2 up to vm. Then, if I look at the path only up to vm, then this is our shortest path from s to vm.

This principle states that any segment or prefix of a shortest path is also a shortest path in its own right. If there were a shorter path from the starting vertex (s) to any intermediate vertex (v), it would contradict the assumption that the path from s to t through this intermediate vertex is the shortest. For example, if the path from s to t involves vertices v1 and v2, then the path from s to v1 must also be the shortest path from s to v1.

Consider a journey where you're traveling from your home to a friend's house and making a stop at a coffee shop on the way. If the route from your home to the coffee shop is the shortest possible route, then it can't be improved by any alternative routes - that portion of your journey is part of the overall shortest trip to your friend's house.

So, we can keep doing Fourier updates, so unnecessary updates and it does not hurt us. So, redundant updates cannot accept this calculation, it just may not make progress, but may not it will not send us to a situation from which we cannot recover the minimum cost.

In algorithms like Dijkstra's and Bellman-Ford, redundant updates (updating paths that have already been found) do not negatively affect the correctness of the algorithm. Although they may slow down the computational process, they ensure that we will never encounter a situation where we are unable to find the correct minimum cost for reaching a vertex. This provides a level of safety in our updating process.

Think of this as double-checking your work in a math problem; even if it feels redundant, checking each step again can help ensure that you didn't miss something important. As a result, when you finally arrive at your answer, you can be confident that it is correct.

So, the Bellman-Ford algorithm basically says do not write to your find the particular sequence, just generally compute all possible sequence have updates. So, at a high level this the algorithm it says initially assigned the distance of s to be 0 and the distance of u to be infinity for every other vertex.

The Bellman-Ford algorithm works systematically to compute the shortest paths by initializing the distance from the source vertex (s) to 0 and all other vertices to infinity. It then performs updates on all possible edges in the graph up to n-1 times (where n is the number of vertices). By iterating through all edges multiple times, the algorithm ensures that it captures the optimal paths, even in the presence of negative edge weights, provided that there are no negative cycles.

Imagine a navigation app that starts with the assumption that you are far away from all your possible destinations (infinity), except your home location (distance 0). It calculates potential routes multiple times, allowing it to continuously refine and find the shortest path to your destination, even if you encounter constructions (negative weights) on your route.

--