m also new to algorithm... anyway... what algorithm r u using??? if u use DFS then there u have to mark the edges u have already visited. hope u have the concepts clear for DFS . if so den u might hv got what i mean.... if not den i cant make u understand.... :-( On 20 Apr 2012 18:55, "vivek dhiman" <[email protected]> wrote:
> Registered order can you explain a bit.. > > > An other geeks and people.... what happened ?? > reply > > 2012/4/20 Registered user <[email protected]> > >> 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. >> >> > > > -- > 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.
