28.1.3. Module – 03

Now, let us look at shortest paths in graphs where we allow Negative Edge weights. In particular let us look at the Bellman-Ford Algorithm.

So, recall that the correctness for Dijkstra's algorithm relied on an invariant property that every vertex that we burn automatically has the shortest path computed at the time when we burn it. However, as we saw this argument does not work if we can have negative edge weights, because we may find later a path via vertex which we have not burnt yet which becomes a shorter path to a vertex we have burnt earlier.

This chunk introduces the concept of shortest paths in graphs, specifically focusing on scenarios where negative edge weights are present. It argues that Dijkstra's algorithm, which is effective when all edge weights are non-negative, fails in this context because the algorithm's foundational assumption—that once a vertex's shortest path is determined, it cannot be improved upon—is not valid when negative weights exist. If new paths involving unvisited vertices are discovered later, they may offer shorter distances than previously computed, which contradicts Dijkstra's approach.

Imagine you're trying to find the quickest route home, and while you initially take a longer route because it seems shortest, you later discover an alternate road that has a construction delay but saves you time overall. This situation is akin to Dijkstra's: once you’ve chosen a path, new information (the construction) might reveal a better option that you didn't consider.

We also said that allowing negative edge weights is one thing, but allowing negative cycles is not a good idea. Because, once you have a negative cycle, you can go around the cycle as many times as you want, it arbitrarily reduces the length of the path, so the shortest path is not even a well defined quantity. So, long as we have negative edges, but not negative cycles, shortest paths do exist and we can hope to compute them.

This chunk focuses on the implications of negative cycles. It explains that while negative edge weights alone can complicate finding the shortest path, the presence of negative cycles leads to ambiguity. Since you could indefinitely traverse a negative cycle and continually reduce the path length, it becomes impossible to define a single 'shortest path'. Therefore, the algorithm can still compute paths as long as negative cycles are absent.

Consider a scenario where you are given a mysterious way to travel such that every time you go in a circular route (the negative cycle), you magically get your travel time deducted. If there was no limit on how many times you could loop around, theoretically, you could reach your destination in negative time, which is nonsensical. This illustrates the issue with negative cycles—a destination effectively becomes unattainable in a defined manner.

So, let us first look at two basic properties about shortest paths which hold regardless of whether the edges can be negative or not, provided we do not have negative cycles. So, the first property is fairly obvious, that is a shortest path will never go through a loop.

The first property established here is that the shortest path between two vertices cannot include loops. If a path revisits a vertex, it can always be shortened by eliminating the loop, as a loop incurs non-negative cost. This means that any shortest path can have at most n-1 edges, assuming there are n vertices. This property allows us to reason about the upper limits of path lengths.

Think of it as taking a scenic drive where you circle back to the same destination. If you realize you’ve taken a detour that returns you to where you started, it’s better to take a direct road instead of wasting time looping back. This emphasizes that when mapping out the fastest route, you can disregard any redundant sections.

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.

This chunk establishes the property that any segment of a shortest path is also a shortest path itself. For example, if moving from a starting point s through vertices v1 to vm and reaching t, then the segment from s to vm must be the shortest route to vm. Any supposed alternative to this shorter route would contradict the definition of the shortest path, reinforcing that each segment retains its optimality within the larger path.

Imagine you're baking a cake and each step is essential for achieving the final product. If you were to skip a key step (like mixing ingredients in order), you would not achieve the desired cake. Each step is necessary and must be optimal; this is similar to segments of a path in shortest path analysis—all must adhere to the property of minimal distance.

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 its neighbors.

This section transitions into Bellman-Ford algorithm analysis. It highlights how Dijkstra's algorithm updates neighbor vertices only after a vertex is confirmed as having the shortest path found. However, in cases with negative edge weights, this approach can lead to incorrect assumptions about previously visited vertices’ distances. Bellman-Ford addresses this by allowing updates even after some vertices have been processed, providing a more flexible and thorough examination of potential paths.

Consider a scenario where you're exploring ways to reach various friends—once you think you've found the fastest way to one friend's house, Dijkstra's method says you can't go back to reassess, but sometimes new hints (like a shortcut) might change the best route later. This flexibility in reconsideration mirrors the essence of the Bellman-Ford approach.

So, we can keep doing redundant updates, so unnecessary updates and it does not hurt us. So, redundant updates cannot affect 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.

This discussion touches on how Dijkstra’s algorithm can become inefficient when negative weights are present, as it can miss optimal paths if it only works by reducing distances through a greedy approach. However, the Bellman-Ford algorithm mitigates potential pitfalls through its inclusive updating process, allowing the reevaluation of distances until all paths are adequately explored.

Imagine regularly checking for the best deals while shopping—you might revisit earlier stores in light of new sales, rather than sticking to the first data you gather. This reflects the iterative nature of the Bellman-Ford method, promoting adaptability until you understand all aspects of your options.

So, Bellman-Ford algorithm basically says do not write to your find the particular sequence, just generally compute all possible sequence of updates. So, at a high level this the algorithm it is 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 operates by setting the starting vertex's distance to zero and others to infinity, performing updates across all edges n-1 times. This exhaustive approach ensures that even if certain paths take longer to optimize, the algorithm iteratively calculates the shortest path by redistributing distances with each cycle, guaranteeing that any valid path is tracked.

Think of it as a group project in school—initially, everyone may have different understandings of the topic (like infinity). Over time, as each member contributes (updates the distances), your collective knowledge improves, ensuring all pathways to the project’s completion are accounted for and refined.

So, let us look at an example and see how the Bellman Ford algorithm actually works. So, here is a graph it has some cycles and it has some negative weights, but there are no negative cycles...

This portion provides a practical demonstration of the Bellman-Ford algorithm in action, illustrating its application in a graph with negative edge weights but no negative cycles. The example shows how initially setting distances and updating neighbors iteratively leads to the shortest paths being calculated effectively, despite the possible complexities introduced by negative weights.

Imagine you’re navigating a city with both express routes (direct paths) and some roads that have roadworks or obstacles (negative weights). While some edges slow you down, the Bellman-Ford approach helps you find the best routes through many iterations to ensure that despite the hiccups, you still arrive at each destination efficiently.

--