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
graph problem
Moderator: Board moderators
Re: graph problem
If the ordering is fixed, then can't the path be found by simply following that order?
Say, I have to go from vertex 1 to vertex 5 and the order is (1 3 4 2 5), then the only path is 1->3->4->2->5? Am I missing something here?
Could you clarify with an example: what do you mean by "ordering is the same as given in the input"
Say, I have to go from vertex 1 to vertex 5 and the order is (1 3 4 2 5), then the only path is 1->3->4->2->5? Am I missing something here?
Could you clarify with an example: what do you mean by "ordering is the same as given in the input"
Re: graph problem
the point is that I am not given all vertices between start and end (I should have mention that, sorry)
I think I've found a better solution - for each fixed vertex I create a subgraph that consists of only two fixed vertices (those that should be "neighbours") and all other non-fixed vertices and using Dijkstra I find shortest path between them; then I move to other two fixed vertices
imagine this:
source: 1
destination: 5
fixed: 2, 3
(number of all vertices = 6)
so first I take vertices 1 and 2 (fixed) and 4, 6 (not fixed) - I find path between 1 and 2
next step: I take 2 and 3 (fixed) and 4,6 (not fixed) - I find path between 2 and 3
the last step: 3, 5 as fixed and 4, 6 as not fixed
so this way I am guaranteeing the order of vertices and that I do not use the same fixed vertex twice (when I use non-fixed vertex twice, that means bad input - that is OK)
I think I've found a better solution - for each fixed vertex I create a subgraph that consists of only two fixed vertices (those that should be "neighbours") and all other non-fixed vertices and using Dijkstra I find shortest path between them; then I move to other two fixed vertices
imagine this:
source: 1
destination: 5
fixed: 2, 3
(number of all vertices = 6)
so first I take vertices 1 and 2 (fixed) and 4, 6 (not fixed) - I find path between 1 and 2
next step: I take 2 and 3 (fixed) and 4,6 (not fixed) - I find path between 2 and 3
the last step: 3, 5 as fixed and 4, 6 as not fixed
so this way I am guaranteeing the order of vertices and that I do not use the same fixed vertex twice (when I use non-fixed vertex twice, that means bad input - that is OK)