Shortest Path Problem

Quote of the day: There are many crooked lines and one straight line. Which is the line of truth? Why the straight line? Truth is always the shortest distance between two points.

 

The shortest path problem is a problem which arises in graph theory (a branch in Mathematics). In brief, Graph theory is the study of a set of objects in which some relation exists between two objects of the sets. Consider a set to be a collection of items and the object being an item in the collection. We can have a collection of pens, a collection of bus stations etc…

 

In graph theory, items or objects are represented using vertices or in other words nodes. And a line is drawn between the nodes to indicate some form of relationship between the objects. Sometimes this relationship is assigned a value which is called a weight. In that case, you will see the number displayed on the line.

 

Here is an example of a graph which is called a directed weighted graph because there are directed lines between some of the nodes and every single line has a weight associated with it.



From the image above, the directed line is used to represent the time it takes to travel between bus stations in a small village, hence the weight number on the directed line representing the time it takes to travel from a station to another station (head of the arrow), like time in minutes.

 

Given these concepts, other concepts are introduced such as a path. Consider a path as a walk which begins at a node, then through the line, and to another node and so on, but ending on a node.

 

With the example above, a path from station 0 to station 2 is 0→ 1 → 5, with the → to indicate the arrow line between the stations.

 

Now, provided the notions of a graph, nodes, and the path, the shortest path problem is a problem of finding a path from a source node to a destination node that minimizes the total sum weight of reaching the destination from the source node.

 

So, for the path 0 to 3, finding the shortest path will give this path: 0→  5 → 3 because it has the minimum total sum weight. Notice that, there are many ways to reach vertice 3 from source 0, but their total sum weight is higher than the path 0 → 5 → 3. Can you list the other paths?

 

How do we find the solution to this problem?

 

The question is an important one but also the most difficult one to answer. The difficult part of this question is that you want to provide a solution that will work on all graphs that are connected and that have lines with weights.

 

There are many algorithms (solutions) to the shortest path problem, some provide the solutions of finding the shortest path between all nodes in the graph. 

 

My next blog post will examine one particular algorithm called dijkstra algorithm. Stay tuned.