i think if u mark the path which u want to block as visited beforehand then u may get it, m not sure but i think it should work.
or if possilbe give the sample input / output cases , den i may solve it.... On 4/20/12, Andrey Ponomarev <[email protected]> wrote: > Hypothesis 1: after eliminating one edge e' the shortest path from a > to b must contain vertex v, such that > neighter sp(a,v), nor sp(v,b) contain e' in the original graph, if > there is such. (Here sp stands for 'shortest path') > Hypothesis 2: if v is some vertex of the modified graph, such that > neighter sp(a,v), nor sp(v,b) contain e' in > the original graph, the shortest path from a to b in the modified > graph is len(sp(a,v)) + len(sp(v,b)). > > If both hypotheses are true then you may try following. In the > original graph build 2 shortest path trees: > one from a and one from b with edges reversed. The first tree let you > at O(1) find len(sp(a,v)), аnd > the second let you at O(1) find len(sp(v,b)). When you have an edge > (v1, v2) removed you should walk > tree1 from v2 and tree2 from v1 and mark all vertices you pass by. > Then you should find one unmarked > vertex with the minimum sum of len(sp(a,v)) + len(sp(v,b)) - it will > be the shortest path and it took O(n). > > 20 апреля 2012 г. 10:48 пользователь vivek dhiman > <[email protected]> написал: >> ok.. >> So if an edge is removed from existing path.Do i have to again find the >> shortest path ? >> >> >> On Fri, Apr 20, 2012 at 11:08 AM, Luke Pebody <[email protected]> >> wrote: >>> >>> Here's a start for you. Find the shortest route. This works as an answer >>> if you remove any edge not in that route. Now you just have to solve it >>> for >>> any removed edges that are in that route. >>> >>> >>> >>> On 20 Apr 2012, at 05:19, vivek dhiman <[email protected]> wrote: >>> >>> Hi all geeks >>> >>> So I have a simple question. >>> >>> Suppose you have a graph G(V,E). >>> You are supposed to find the shortest path from a vertex 's' to vertex >>> 'e' >>> for 'n' different cases. >>> >>> In each case one of the edges 'Ei' (any one edge) of the graph will be >>> blocked/deleted only for that case and we have to find the shortest path >>> in >>> the graph with that edge removed. >>> >>> Guys finding the shortest path is easy. But how can I make the algo so >>> fast that even if I remove one of the edges my algo should still be very >>> fast. O(n log n) or faster. >>> Remember we are not deleting the edges permanently. We are just temporary >>> removing one edge per case. >>> In each case only one edge is removed. >>> Suppose we blocked one edge E in one case. We have to find the shortest >>> path for the graph. >>> In next case, we will reconnect the last edge and we will block/remove a >>> new edge. And again for this new case we have to find the shortest path. >>> >>> Another way of understanding the problem is suppose there are cities >>> connected to each other. >>> And every day one of the roads gets blocked because of heavy rain. what >>> is >>> the shortest path every day from city s to e. >>> Also one more important thing to note that each road can be used only >>> once. >>> But there could be more than 1 direct road from city a to city b. >>> >>> FInd the shortest path distance from city s to e on a day when all direct >>> roads from city f to city h are blocked. If there is no connecting path >>> return -1 >>> >>> Thanks and Regards >>> Vivek Dhiman >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Google Code Jam" 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/google-code?hl=en. >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Google Code Jam" 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/google-code?hl=en. >> >> >> >> >> -- >> Regards >> Vivek Dhiman >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Google Code Jam" 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/google-code?hl=en. > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" 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/google-code?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" 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/google-code?hl=en.
