there is an example of BFS fail: - - - 2 ---- 6 - - - -- 7 - - - - - S / -- - - - - - / F - - - 3- - - - 4 - -- - - 5 - -- - - -
going form S to F. k = 2. BFS finds path S37F, as it is shortest. After removing this path there is no other path from S to F. But choosing paths another way you could get 2. About restrictions on vertexes - it is rather well known trick. You double each vertex and get 2 vertexes V' and V''. Make all the graph directed. There is an edge from V' to V'' with capacity equal to vertex initial capacity. All in-edges come to V' all out-edges go from V''. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
