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.
