26.1.7.2. Formal Algorithm Description

Let us turn our attention now to weighted graphs, graphs in which edges have cost associated with them. The most important thing that we can do with weighted graphs is to compute shortest paths.

We look at what happens if we add costs to the edges... the total cost that we pay for a ticket will be the sum of the cost. So, we will extend weights from edges to paths by just adding up the sum of the weights along each path.

In this chunk, we learn that weighted graphs have edges that carry costs. The goal is to determine the shortest path based on these costs rather than just the number of edges crossed. For example, in an airline routing map, the edge weight could represent the ticket price, while in a traffic map, it might represent travel time. We accumulate these weights to define the total cost of traveling from one vertex to another along a path.

Imagine planning a road trip using a map where distances represent fuel costs instead of miles. You want to save money, so you're looking for the route that costs the least, even if it may take longer in terms of time.

We can ask two types of question regarding shortest paths, one is so called single source path... The other problem would be to compute the shortest distance between any pair of vertices.

This chunk discusses two types of shortest path problems. One is the 'Single Source Shortest Path Problem,' where you start at one vertex (like a distribution center) and wish to find the shortest distances to all other vertices. The second is the 'All Pairs Shortest Path Problem,' where you need to calculate the shortest paths between every pair of vertices in the graph. Both problems have practical applications in areas like logistics and routing networks.

Imagine you're a food delivery service. The single source shortest path problem could involve finding the quickest route from your restaurant to every customer in the area. Conversely, the all pairs shortest path problem would help you plan the best delivery routes between any two restaurants in your network.

So, we will begin by looking at this single source shortest path problem. So, we have to design, we have to designate in such a problem, what is the start vertex... The systematic way to compute this.

This chunk introduces Dijkstra's Algorithm, a systematic approach to solve the single source shortest path problem. Here, you begin by selecting a start vertex. The algorithm uses a method similar to a fire spreading through edges. It calculates the 'burning' time, or the cost of reaching neighboring nodes. As the algorithm progresses, it updates the shortest known distance from the start to each vertex until all vertices have been 'burned' or processed.

Think of it as a wildfire spreading through a forest. It starts at a single point and moves to nearby trees (vertices) based on the most accessible routes (shortest paths). As the fire reaches each tree, it marks the shortest path cost (time) taken to get there.

So, let us see, how we would actually compute this burning process that we describe. So, what we do is we associate time to the shortest distance as a quantity with each vertex... and the value of burn time, through this vertex.

In this chunk, we delve deeper into how the burning process works with the algorithm. Initially, every vertex is set to unreachable with an 'infinity' burn time, except for the source vertex, which is set at '0'. From there, as we process vertices, we check neighboring vertices and update their burn times based on the discovered paths, effectively 'burning' through the graph until all connections have been evaluated.

Picture a city firefighter responding to a blaze. They can't spread water everywhere at once. Instead, they assess the fire's spread, targeting the places that are most in danger first, managing resources effectively while ensuring they reach all areas with the quickest response times.

So, to write this formally as an algorithm, we maintain this information about the burnt, but vertices... so we choose the smallest unplanned vertex.

This chunk summarizes how to formalize the burning process into a structured algorithm. We keep track of which vertices have been processed and their burn times with two arrays: one for tracking burned vertices and another for the expected burn time. In the algorithm, we constantly select the vertex with the smallest burn time and update the burn times for its unprocessed neighbors. By systematically repeating this process, we efficiently find the shortest paths.

Consider this approach as similar to how GPS systems work. As you drive, the GPS continually updates the estimated arrival times to your destinations based on real-time traffic conditions, taking the quickest, least expensive routes as it processes new data.

--