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.
