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.
There is only one road from one city to another
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.
