28.2.1. Introduction to Negative Edges

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.

In this section, we introduce the concept of finding the shortest path in graphs that have negative edge weights. Unlike positive weights, negative weights can complicate the calculation of the shortest path because they can lead to situations where the shortest path can be influenced negatively. The Bellman-Ford Algorithm is designed to handle these cases effectively.

Think of a map where some routes offer discounts (negative weights) instead of tolls (positive weights). If you only take into account the distances normally, you may miss out on the quickest and cheapest route that leverages those discounts effectively.

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.

Dijkstra's algorithm is effective for graphs with non-negative weights because once a vertex is finalized, its shortest path is guaranteed. However, if negative edge weights are present, a path to a vertex could become shorter after it has already been finalized, invalidating the previous assumption of correctness.

Imagine you're on a road trip and you have to decide on routes in advance. If you take a route that seems the fastest (finalized), but later find a shortcut that wasn't initially visible (a negative weight), your earlier choice is no longer the best one.

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, around 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.

Negative cycles can severely disrupt the concept of 'shortest paths' since you can keep traversing the cycle repeatedly, lowering the total path weight infinitely. It is crucial to handle graphs with negative edges correctly while ensuring that negative cycles do not exist.

Think of a ride-sharing app offering discounts for certain routes. If the discount is so great that you can keep taking the same route repeatedly, you'd keep getting lower and lower costs, making it impossible to define a 'final' cost for that journey.

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.

The first property states that the shortest path will never include loops; going in circles only adds unnecessary distance. The second property affirms that if a path from 's' to 't' includes intermediate vertices, any subpath must itself be the shortest path, reinforcing the idea that shorter paths cannot emerge from longer ones.

Consider a trip from your home to your friend's house. If you take a direct road instead of looping through places you've already visited, you're certainly going to arrive sooner. Similarly, every short detour along the route (subpath) should be the quickest way to get to the next point.

So, these two properties are enough for us to arrive at the Bellman-Ford algorithm for shortest path in the presence of negative edge weights.

The Bellman-Ford algorithm utilizes the two properties discussed to ensure that even with negative weights, the shortest path can be computed. By systematically checking paths and updating distances, it ensures that no path is missed even if certain edges were negatively weighted.

Imagine being in a maze where some paths are longer but offer shortcuts. The Bellman-Ford algorithm is like a methodical approach where you explore all possible paths to make sure you find not just any path, but the shortest one, even if some paths appear misleadingly longer.

In Dijkstra's algorithm whenever we burn a vertex, we update all its neighbors. The correctness of Dijkstra's algorithm says that when we burnt j, the distance to j is the correct distance to j.

The update operation in Dijkstra’s algorithm ensures that when a vertex is finalized (burnt), all its neighbors' distances are recalculated and set to the smallest possible values. This is crucial in ensuring that later updates do not inadvertently miss shorter paths.

Think of this update as marking all your friends' homes from your own until the moment you decide which one to visit. Once you finalise a friend to visit (burnt), you check each friend's home nearby to see if it’s worth a visit instead. This dynamic adjustment lets you make better travel decisions based on current information.

Bellman-Ford algorithm basically says do not write to your find the particular sequence, just generally compute all possible sequence have updates.

The Bellman-Ford algorithm works by repeatedly applying updates across all edges in the graph for 'n-1' iterations. This is because the longest path between two vertices can contain at most 'n-1' edges (for 'n' vertices), ensuring that the algorithm thoroughly explores all potential paths.

Imagine taking a basemap of your city and choosing every possible route to a destination over a series of days. No matter how convoluted your paths are, by the end of your exploration (n-1 iterations), you will have reduced your choices to the most efficient route available based on your travelling experience.

--