Hi,
could you please help me with this problem (it is not contest-related problem):
I have got a weight undirect graph and a list of vertices I have to visit
I want to find shortest path (from source vertex to destination vertex) with no cycles, I have to visit each vertex exactly once (also order of vertices is important - it must be the same order is given in input) and I cannot use one edge twice
my current solution is pretty brute-force:
first I find all possible paths between two given vertices using Breadth-first search ; after that I calculate how long is each path and sort these paths from shortest to longest
the next step is to iterate through all paths (begining with the shortest one) and check if I have visited all given vertices and in correct order
instead of BFS I was also thinking about Floyd–Warshall algorithm, but I don't think I can find all paths between two vertices using Floyd-Warshall
could you pls help me how to solve this? (because my solution is .... well...)
I don't really care about time complexity - there will be max 10 vertices and not too much edges, so no big deal
thanks a lot