graph problem

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
New poster
Posts: 4
Joined: Sun Dec 02, 2007 8:09 pm

graph problem

Post by Piotr42 » Thu Feb 02, 2012 9:42 pm

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

User avatar
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: graph problem

Post by sohel » Fri Feb 03, 2012 5:04 am

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"

New poster
Posts: 4
Joined: Sun Dec 02, 2007 8:09 pm

Re: graph problem

Post by Piotr42 » Fri Feb 03, 2012 9:09 am

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)

Post Reply

Return to “Algorithms”