[SOLVED]Dijkstra, but passing through some nodes

Question

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!

Answer 1

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!

Answer 2

https://geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/

Answer 3

Stefan Secrieru what is meant by road 244?

Answer 4

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.

Answer 5

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).

Answer 6

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.

Answer 7

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...

Answer 8

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

Answer 9

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

Answer 10

Stefan Secrieru care to share your reasoning?

Answer 11

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