Блог пользователя c___a_

Автор c___a_, история, 7 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +28
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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 .

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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]

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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?

            • »
              »
              »
              »
              »
              »
              »
              7 лет назад, # ^ |
                Проголосовать: нравится +1 Проголосовать: не нравится

              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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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)

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      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.