c___a_'s blog

By c___a_, history, 5 weeks ago, In English,

We are given 2 nodes s and t, and M queries that have one edge that needs to be deleted [only for this query], and for each query you need to output the shortest path between s and t. Note that s and t do not change.

1 ≤ Number of Nodes ≤ 7000

1 ≤ Number of edges ≤ 50000

1 ≤ Number of queries ≤ 10000

I couldn't find anything over the internet. I was thinking of something along the walks of pre-computation on a Dijkstra tree/Shortest path tree but couldn't think of anything. Can someone please provide hints or an approach to this problem?

 
 
 
 
  • Vote: I like it  
  • +28
  • Vote: I do not like it  

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Does deletion means turning weight to 0 and keeping the edge or complete removal of the edge?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I dont know how MaxFlow/Min Cut works. But this link may help you

https://stackoverflow.com/questions/10895259/shortest-path-in-absence-of-the-given-edge

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I've seen that link, but there exists a much simpler solution not involving Max Flow/Min Cut I believe

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      The word "cut" does not mean that you need some mincut algorithm. Let's explain it in other words.

      For a given edge e we can define two sets of edges: and . path(x, y) is some shortest path between x and y. We will assume that , otherwise the answer is obvious.

      It's easy too see that each vertex lies either in A or in B. Consider the earliest moment when we go from the vertex in to the vertex in . By definition, we can go from s to x by the shortest path in the original graph, the same is true for y and t. So the path is uniquely determined by the edge xy. We just need to go through all edges xy such that and .

      It works in O(qm) for queries and for shortest paths precomputations. Also there is a way to sped up it to .

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That makes sense, I understand your solution, thanks! But for each such edge xy, we have to iterate through all edges in our shortest path and update the answer for this edge in our pre-computation right?

        Doesn't that make the complexity O(M*N) rather than O(MlogM)? [since there can be at most N edges in the shortest path]

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          No, for each edge xy we just use precomputed values of d(s, x) and d(y, t) in the original graph.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Couldn't the path d(s,x) -> edge xy -> d(y,t) be an answer for all edges in our shortest path d(s,t)?

            So we're iterating through all such edges xy and updating the answer for all edges in our shortest path during pre-computation, right?

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              No, in precomputation we only build two Dijkstra trees, from s and from t. We need them to find sets A and B.

              For each query we find A and B, iterate through edges, and find the answer.

              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                But won't O(qm) time out for the given constraints?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't this the Facebook problem from ioitc 2012?!

»
5 weeks ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

Since answer for edges not on original shortest path is the same, ignore those.

Consider the dijkstra/shortest path tree of the graph from s. In this, if you delete an edge on the shortest path to t, the tree splits into 2 parts, if you can appropriately find the "bridge" between these 2 components, you can solve the problem.

For finding that, consider an edge (u, v, d) not in the original dijkstra tree. Assume in the dijkstra tree , The shortest path going via this edge has weight D(s, u) + D(v, t) + d where D(a, b) = distance b/w nodes.

So this edge may form the shortest path bridge when we disconnect some other edge on path(u, v) in the tree. This reduces the problem to path update + edge query, which can be handled offline(or with HLD).

Time complexity: O((N + Mlog(N + M) + Q)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks! But how do you handle offline processing efficiently? I can't think better than O(M*N)

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      You can just use straightforward HLD.

      Or, since you only need to worry about edges on path s -> t, this is equivalent to saying you have an array of edges b/w s to t sequentially(each having value infinity) and some range updates (L, R, w) which describe “set the value of all elements between (L,R) to min(current value, w)”, this can be done using set or something and iterating from left to right, activating and deactivating the updates.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think I understand. But suppose we have an edge (u,v,d) : how do we decide the (L,R) values [or the sequential edges] in our linear path that this edge can affect?