suppose if we have given weighted graph and we traverse through city 1 to other cities i.e. from 1 to n…and we have to find smallest path to reach each city by city 1 but condition is that there are toll tax system in every path which is given …
then it is very easy to find shortest path using dkshitra algorithm …
BUT one more condition is thaT you can leave at most k path in finding each shortest path ,it means we do not add at most k path i.e. toll tax to our solution then how you can find it??/
k can be 1< k <=18
IN MY idea ,we can add to each path to vector and using sort , delete at most k path and add ,find the required answer…
Please explain briefly with some optimisation
@AMIT_KUMAR
If you do that then it may give wrong answer, because consider a case when there are two paths between A and B with weights as
- 10 5 10 1
- 1 100 1
then in that case you will find the 1st one and remove some weights from it but here if you have selected the second case, just by ignoring 100 you will get that.
@AMIT_KUMAR
One thing we can do here is traverse recursively and for every edge we check all the possibilities by either taking or not taking that particular edge (do this for every edge till k>0) and find the solution for whole accordingly.
You can also try to optimize using Dynamic Programming later on based upon the conditions if possible in the problem.
It will better to discuss and optimize the problem if you can provide the link to actual problem.
If you just asking for clearing concepts and discussion then you can also ping me over chat.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.