1.2. Characteristics of Shortest Paths

Let us now turn our attention to the All-pairs Shortest Paths problems, where we try to find the paths, shortest paths between every pair of vertices in a graph.

In the context of graph theory, a shortest path is defined as the minimum distance (sum of weights) needed to travel from one vertex (node) to another in a weighted graph. The All-pairs Shortest Paths problem seeks to identify the shortest paths for every pair of vertices in that graph. This is essential in various real-world applications such as network routing, navigation systems, and optimizing transportation.

Imagine you are using a GPS navigation system to find the fastest route between multiple cities. The process of calculating the shortest route from every city to every other city reflects the All-pairs Shortest Paths problem.

So, you made the following observation of shortest paths that the shortest path even in the presence of negative weights will never loop, because we can always remove the loop without increasing the length of the path.

One key characteristic of shortest paths in graphs is that they do not contain cycles or loops. If a path were to revisit the same vertex, the journey could be made shorter by eliminating those repeated sections. This means that in any valid shortest path from vertex i to vertex j, no vertex can be revisited; thus, a valid shortest path's length can be at most n - 1, where n is the number of vertices.

Think of a road trip where you are trying to minimize travel distance. If you drive in a circle (loop) and pass the same landmarks multiple times rather than taking a more direct route, you're wasting time and distance. The optimal choice would be to avoid unnecessary detours.

We will come up with an inductive solution of how to build up the shortest paths.

The approach to finding All-pairs Shortest Paths can involve induction. This means that we start by establishing the shortest paths that only connect certain pairs of vertices, gradually increasing our constraints to include additional vertices. By examining the shortest paths that use up to the k-th vertex and comparing them with those that don't, we can iteratively improve our estimates for shortest paths.

Consider solving a puzzle that involves finding the quickest way to connect several towns. You could start by establishing the shortest route between a small number of towns first and then use this knowledge as you progressively include more towns, leveraging previous discoveries to find longer routes.

So, the simplest shortest path you can imagine in a pair of vertices it is just a single edge. But, in general this may not be the shortest path, because... there may be a way... of reaching from i to j by our longer path of edges, but to the shorter overall cost.

Initially, the shortest path between two vertices could be a direct edge. However, due to the presence of negative weights, alternative routes that traverse through intermediate vertices may yield a shorter total distance. Thus, the final shortest path may involve visiting multiple other vertices instead of going directly.

Imagine that you're trying to buy a product online. A direct purchase from one store might seem quickest but if you search for discount coupons and compare shipping costs by going through other links (intermediate sites), you may find a route that’s more cost-effective overall.

Now that we know the shortest paths which use 1 to k - 1, how do we compute the shortest paths using 1 to k?

In the inductive process, once we have established the shortest paths considering k - 1 vertices, we can now explore the addition of a k-th vertex. We evaluate if introducing the k-th vertex would result in a shorter path. If it does not provide an improvement, we retain the previous recorded shortest distance.

Think about planning a trip where you initially mapped out your route. After mapping, you find a new scenic roadway that may not provide a shortcut. If the scenic route doesn't help you reach your destination faster, you'd stick to your original plan.

This gives us an immediate algorithm which is called the Floyd-Warshall algorithm.

The Floyd-Warshall algorithm implements the inductive logic discussed earlier. It starts with an initial distance matrix based on direct edges and iteratively updates this matrix to account for shorter paths using all possible combinations of vertices. The result is a matrix that captures the shortest paths between all pairs of vertices in the graph.

Imagine a travel planner app that keeps updating shortest travel times as you check various routes. Initially, it provides direct routes between cities, and then updates these routes based on new data about travel times as more ways to travel become available.

--