[SOLVED]Dijkstra, but passing through some nodes

Hi, SoloLearn. I was wondering: using the Dijkstra's algorithm, how can I find the smallest distance between node 1 and node n, knowing that I must pass through some nodes along the way. E.g: we have 4 nodes and 5 roads(bidirectional), I must get from node 1 to node 4 and also visit node 2 The roads: 1 2 1 1 3 1 2 3 1 2 4 4 3 4 2 The shorthest path is: 1-3-4 that costs 3 but if I visit the second node the path becomes: 1-2-3-4 cost:4 Thank you for your time!

8/23/2019 1:14:14 PM

Stefan Secrieru

11 Answers

New Answer


So after a long time, I realised that it got something wrong: the number of the "must-pass" nodes was actually lower or equal to 15 not 2000. It looks something like this : 0 ≤ K ≤ min{15, N – 2}, I just did not see the "min". Thank you for your help, everyone. After all you calculate the minimum distance between the first, the last and every must-pass node and then you use TSP to solve it as there are no more than 15 must-pass nodes.It also means that you can not solve this for a big number of must-pass nodes in short times( polynomial time ) as the TSP is NP. Thank you for your time. Farewell!




Stefan Secrieru what is meant by road 244?


Thank you, Prometheus. I have the feeling that this problem is actually more related to Kruskal's algorithm than to Dijkstra's. Thank you for the help.


Sonic , road 2 4 4 means that the node 2 is connected to node 4 and the cost of travelling between them is 4. Also the node 4 is connected to node 2(the roads are bidirectional).


Monical I tried to do it using the Travelling Salesman Problem with dynamic programming, but it is indeed a NP problem, so the time it takes is very long and my problem says that it must be solved in under 1 second. Note: there can be a maximum of 2000 nodes, so I also can not use a bitmask . Don't get me wrong, it works using TSP but I need to somehow do it faster. Now I am still trying a different approach using some sort of Dijkstra.


Another ideea is to calculate using Dijkstra the minimum distance between node 1 and all of the must-pass nodes, between the must-pass nodes and the sink, and between the must-pass nodes and the other must-pass nodes. After that I created another graph containing only the mandatory nodes, start, and sink. But now I back to TSP again...


Monical I will try to use that method, thank you for the ideea.


This is like car pooling, same destination but you have to pickup people


Stefan Secrieru care to share your reasoning?


Stefan Secrieru would you consider using a branch and bound algorithm?