+6

[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

0

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!

+4

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

+3

Stefan Secrieru what is meant by road 244?

+2

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.

+1

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

+1

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.

+1

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

+1

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

+1

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

0

Stefan Secrieru care to share your reasoning?

0

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