Is there an algorithm for finding the shortest path in a graph with multiple points?

Question

PHP

Hello, dear IT-specialists.
The essence of the problem. There are several multi-storey buildings. In each of them, on each floor there are rooms.
Task.
At the entrance, the user indicates the rooms (usually from 2 to 10, somewhere) that he needs to get into in one round within all floors of all buildings.
And at the output should get the shortest route around these points.
And looking for something like this on the Internet did not come across.
Whether there is an experience of the decision of similar tasks?. Or representation where to dig can?
PS We write in php with a mysql database . The project is not highly loaded. It is possible to use a smart server.

Answer 1

With your limitations, a brute-force solution will do.
First, we use Floyd's algorithm to find all the shortest distances between the selected vertices.
Then we sort through all the bypass sequences and calculate the minimum. There will be 10 such sequence! = 3.6 * 10^6 even on the simplest computer should take no more than a second.

Answer 2

This is the traveling salesman task. For 10-20 rooms is solved through dynamic programming. For more, you need to look at specific data. If I understand correctly, you can solve the problem for each building separately, then combine them.

Answer 3

Either you did not specify all the conditions, or the task is very simple.
Answer: build a passage through all the rooms in the context of one floor, then the next floor (where you need to go)

Answer 4

With so many points, you can use the simplest wave algorithm.
https://www.youtube.com/watch?v=9ev9Y-hJhj4
Of course, when calculating the wave, you need to take into account the weight of the ribs, in my opinion there is no such thing in the video.