find the shortestS paths in an unweighted graph by

Question

My problem is that I want to find the shortestS(most possible paths) between a vertex S and T in a graph, but I have a flow constraints too, because the problem state:

-you have a number of ants(or whatever) / a number of rooms / and a number of links between them, I've to send my ants one turn at a time, from S through my graph, to reach T, but all rooms can contains only one ants at a time except for S and T and the ants may not get stuck in a room during several turn.

so I've a flow graph with all the edges with capacity of one (to respect the no more than one ants in each room).

And here I end up with a problem which is between max flow and shortest path, because some shortcuts between two paths could exists, sometimes if I've only one or a little number of ants, that'll be better to take just one path (take the shortcut) and send my ants in single file, but at a certain number of ants it'll be better to take two path, not use the shortcut and send my ants two by two, one in each path, by doing so i'll end up with fewest turn for pass all my ants from S to T.

So far I've found some good algorithms for shortests path, but they always gave me the wrong answer, because they could find blocking flows, meaning take one shortest path instead of two which could have been better, to avoid this problem I've look to max flow problem, with algo like ford fulkerson, because I can track blocking flow and reverse them by looking precisely at if it's worth to reverse a shortcut according to my ants, but there's no notion of weight, so all the shortcut (which will be reverse by max flow algo, because shortcuts are the only things that could cause blocking flow), will be reverse but randomly, so that's harder to prove but i'm pretty sure that that's wrong too, I think it's a better and more precise way to do it than only a shortest path algo, but I'm sure it's again not correct at 100% specifically with graph containing a lot of shorcuts.

So yes it's school work, and I don't want my homework to be done by you, but I really want to go into this subject in depths, and I'm a beginner in all the graph stuff, so I'm interested into any algorithm that could help me, or whatever that could help!

Answer 1

I think you are on the right path looking at maximum flow algorithms. You could try the following three step approach:

1. Rebuild your graph in order to incorporate your (only one ant per room constraint). This can be done by replacing each room vertex v by two vertices v_1, v_2 and a directed edge e(v_1, v_2) with capacity 1. All incoming edges to v are connected to v_1 instead. All outgoing edges of v are connected to v_2 instead. This way only one ant can go through v (e(v_1, v_2)) at any point in time. Each initial edge between two rooms also gets a capacity of 1.
2. Run the Ford–Fulkerson algorithm. This should tell you which edges to use in order to maximize the flow. In fact this should give you all distinct paths (where no two paths share a room) from S to T.
3. Once you have the distinct paths, you can calculate their lengths and from that it should be straightforward to calculate the necessary number of steps to get all ants from S to T.