26.1.5.1. Single Source Shortest Path Problem

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

Weighted graphs differ from unweighted graphs in that the edges connecting the vertices also have associated costs or weights. In many applications, these weights represent real-world values, such as distances, costs, or time needed for traversal. The primary task when dealing with weighted graphs is calculating the shortest paths between various points, which is not limited to just number of edges, unlike unweighted graphs.

Imagine planning a road trip where each road has a different fuel cost associated with it. Some roads might be shorter, while others may consume more fuel. In this case, you would want to choose a route that minimizes fuel costs rather than just the distance.

In general, weighted graphs contain a weight function that assigns a real number cost to each edge. For example, the edge weight could represent ticket prices for flights, toll fees on roads, or distances/travel times between locations.

The cost associated with each edge in a weighted graph reflects the difficulty or expense involved in traversing that edge. The weight function provides a systematic way of understanding how to compute the total cost of a path by summing the weights of all edges present in that path, allowing us to identify the least expensive route.

Think of a grocery delivery service that charges based on distance traveled. Every road taken has a different cost based on traffic or tolls. If you want to get groceries delivered at the lowest price, you would want to choose the path that has the lowest sum of costs, not just the shortest distance.

In the single source shortest path problem, we designate a starting point in the graph and want to find the shortest distance (minimum cost) to every other vertex from this starting point.

The single source shortest path problem involves calculating the shortest paths from one specific vertex (the source) to all other vertices in the graph. This is beneficial in various real-world scenarios, notably in logistics and delivery systems, where one central location needs to deliver goods efficiently across multiple destinations.

Consider a delivery truck that starts from a warehouse (the source) and needs to reach various delivery points (addresses) in a city. The task is to figure out the quickest routes from the warehouse to each delivery point, ensuring that fuel and time are minimized.

We can ask two types of question regarding shortest paths. One is single source, which finds the shortest path from one source to all other destinations; the other computes the shortest path between any pair of vertices.

There are two distinct problems concerning shortest paths in graphs: the single-source shortest path problem and the all-pairs shortest path problem. The single-source approach focuses on one starting point, while the all-pairs seek to determine the shortest paths between each pair of vertices within the graph.

Imagine using a navigation app. When you select your home to find the fastest route to every restaurant in the area (single-source), that’s the single-source shortest path problem. Conversely, when you check the best route between any two specific restaurants (any pair), you're dealing with the all-pairs shortest path problem.

We begin by looking at the single source shortest path problem, where we denote the start vertex and systematically compute the shortest paths to all other vertices.

Dijkstra’s Algorithm is a well-known method for solving the single source shortest path problem. It involves marking the starting vertex with a distance of zero and all others as 'infinity'. As the algorithm processes the vertices, it updates the shortest known paths based on edge weights until all vertices are determined.

Using the delivery truck analogy, think of Dijkstra's Algorithm as a driver who initially knows the distance to their warehouse (zero) and views all other locations as far away (infinity). As they drive and gather information about the quickest routes, they adjust their understanding of distance to each delivery point.

--