26.1.1. Introduction to Weighted Graphs

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.

Weighted graphs are similar to regular graphs, but each edge has an associated cost or weight. This cost can represent various metrics such as distance, time, or financial cost. The primary goal when working with weighted graphs is to find the shortest path — that is, the path that minimizes the total cost incurred when traveling from one vertex to another.

Imagine planning a trip. You have a map with various routes, each having a different distance and travel time. A weighted graph helps you optimize your travel by finding the route that takes the least time or distance, depending on what matters most to you.

So, let us review what we have seen so far. We have been looking at unweighted graphs, where each edge is just the connection between two vertices. We explored breath first search and depth first search.

In unweighted graphs, the focus is solely on the connections between vertices, with no regard for the cost of edges. We typically utilize two main algorithms — breadth first search (BFS) and depth first search (DFS) — to traverse these graphs. BFS explores vertices level by level while ensuring the shortest path in terms of the number of edges is found, whereas DFS goes deep into the graph, potentially skipping shorter paths.

Think of BFS as searching through a library by checking each shelf one by one while ensuring you don’t skip any books on a shelf. DFS, on the other hand, is like diving deep into a section of the library and exploring all the books there before coming back to check other sections. Both methods have their usefulness depending on the goal.

Now, we look at what happens if we add costs to the edges. Depending on the application, this cost has several natural interpretations, such as ticket prices on flights or tolls on roads.

Once costs are assigned to the edges of a graph, the representation changes significantly. For example, an airline routing graph might have flight costs as weights. Similarly, a road graph could display toll prices. Assigning costs essentially means we need to consider these weights when calculating paths, particularly for finding the shortest path between two points.

Think of a delivery truck that needs to determine its route. It not only cares about the distance between stops but also the costs associated with tolls, fuel, or time delays. Calculating the shortest (most cost-effective) path is crucial for maximizing efficiency.

So, we will extend weights from edges to paths by just adding up the sum of the weights along each path. And now, a natural problem is to find the shortest path between a given pair of vertices.

In a weighted graph, the total cost of traveling from one vertex to another is calculated by summing the weights of each edge that lies on the path connecting those vertices. The goal now is to determine which path gives the minimal total weight, which may not always correspond to the shortest path in terms of the number of edges.

Consider a shopping scenario where different stores have varying shipping fees for each product. If you were to buy multiple items from different stores, you'd need to calculate the total shipping cost for each shopping method and select the one that incurs the least cost overall.

We can ask two types of questions regarding shortest paths: single source shortest path and shortest path between any pair of vertices. These represent different types of problems we can solve using weighted graphs.

The single source shortest path problem focuses on finding the shortest paths from one starting vertex to all other vertices in the graph. In contrast, the all-pairs shortest path problem seeks to find the shortest paths between every pair of vertices. Both problems are significant in various applications like transportation networks, where optimizing routes is crucial.

Imagine a ride-sharing app: for a single source problem, it would calculate the best routes from a central location to various drop-off points. For the all-pairs shortest path problem, it would compute the best routes between every pair of locations, helping users compare their options.

We will begin by looking at this single source shortest path problem. We have to designate what is the start vertex. Here we have a graph with 7 vertices...

Dijkstra's Algorithm is a process for solving the single source shortest path problem. The algorithm starts at the designated vertex and explores all possible paths to calculate the minimum cost to reach each other vertex. It systematically updates the shortest paths and 'burns' vertices as it finds their shortest distances.

Visualize lighting a fire at a central campfire in the woods. The flames represent spreading warmth to nearby cabins (vertices). As time passes, the fire reaches closer cabins first before spreading farther. The time it takes for the fire to reach each cabin could symbolize the shortest path cost from the campfire to that cabin.

--