Find all Paths in a Graph
Hey coder, welcome to a new problem of graphs. This is a multisolver question in which we will find the required paths.
The prerequisite of this question is "Print All Paths", so make sure to check it out.
- You are given a graph, a src vertex and a destination vertex, a number named "criteria" and a number "k".
- You are required to find the smallest and largest paths between the src and destination vertices.
- Also, you are required to find a ceil path (just larger path in terms of weight) and floor path (just smaller path in terms of weight) to the given weight "criteria".
- At last, you must find the kth largest path in the graph.
- Reader, you have already done the problem "Print All Paths". If you can find all the paths, then you can definitely find out the required paths in this question.
- To understand this problem we consider the following graph where drc and destination vertices are 0 and 6, "criteria"=40 and k=3.
In the above graph, all possible paths along with their weights are listed below.
From this, we can deduce that:
- The shortest path is A as it has the least weight i.e. 38.
- The largest path is B as it has the maximum weight i.e. 50.
- The ceil path (just larger path) to criteria=40 is C with weight 48.
- The floor path (just smaller path) to criteria=40 is A with weight 38.
- The kth=3rd largest path is C.
Let's now discuss the strategy to solve this problem.
Reader, we will discuss each part of the problem one by one.
When src and destination vertices are equal, if the weight so far (wsf) is less than the smallest path weight (spathwt) then the value of spathwt gets updated to the value of wsf. Hence, our smallest path (spath) is the path so far (psf).
- Largest path:
When src and destination vertices are equal, if the weight so far (wsf) is greater than the largest path weight (lpathwt) then the value of lpathwt gets updated to value of wsf. Hence, our largest path (spath) is now the path so far (psf).
- Ceil path:
To find the ceil path, we need to find the smallest weight out of all the weights larger than the criteria. To do so, we first need to check if the weight so far (wsf) is greater than the given criteria. Also, wsf needs to be smaller than the current ceil path weight. If these conditions are fulfilled, then cpathwt is updated to this wsf and cpath becomes the path so far (psf).
- Floor path:
To find the floor path, we need to find the largest weight out of all the weights smaller than the criteria. To do so, we first need to check if the weight so far (wsf) is smaller than the given criteria. Also, wsf needs to be larger than the current floor path weight. If these conditions are fulfilled, then fpathwt is updated to this wsf and fpath becomes the path so far (psf).
- Kth largest path:
To find the kth largest path we make use of Priority Queue.
We have already discussed the concept of Priority Queue in "Introduction to Heaps", so check that out if you haven't already.
In a Priority Queue, the numbers can be added in any order but those numbers which have the highest priority are removed from first.
By default, priority queue is a minimum priority queue i.e. the minimum number out of all the elements in the queue will be removed first.
In our problem, if k=3, then the priority queue must always have 3 elements in it.
So, when we keep removing the minimum number from the priority queue while traversing through all the elements, at last the priority queue will store the 3 largest elements in it. At this point, the element that will be removed will be the smallest of the 3 largest elements, hence it is the 3rd largest number out of all the elements.
We highly encourage you to watch the solution video of this problem to get a better grasp of the strategy in your mind.
Reader, the full code for this problem is given below.