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

Автор frying_pan, история, 10 месяцев назад, По-английски

Given a weighted directed graph $$$G$$$ and $$$2$$$ different vertices $$$s$$$ and $$$t$$$ in it. How can we find all edges $$$e$$$ such that removing $$$e$$$ increases the distance between $$$s$$$ and $$$t$$$? Is there a better way then $$$O(E*E*log(V))$$$ time method where we test each edge by removing it? Can we also find all vertices $$$v$$$ defined analogously?

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

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

Auto comment: topic has been updated by frying_pan (previous revision, new revision, compare).

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

Auto comment: topic has been updated by frying_pan (previous revision, new revision, compare).

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

let d1[i] be the minimum distance from s to i.

let c1[i] be the number of paths whose distance from s to i equal to d1[i].

let d2[i] be the minimum distance from i to t.

let c2[i] be the number of paths whose distance from i to t equal to d2[i].

let "t" be the minimum distance from s to t.

let "num" be the number of shortest paths from s to t.

we will count the number of edges (u->v) that d1[u] + d2[v] + len of edge(u->v) == t and d1[u] * d2[v] == num

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

    This algorithm is correct, but when there are many edges in the graph the number of shortest paths may be too large to store efficiently, and using modulo will lead to some false equalities.

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

One possible idea is to construct the "shortest-path graph" between S and T (there might be a better name for this, but it will do for now). This graph consists of all edges that lie on some shortest path between S and T (and their endpoints as nodes). We can compute this graph by running Dijkstra's algorithm twice — once from S and once from T. (when running from T, you will need to invert the edges.) Then, an edge's removal will increase the distance from S to T if and only if it is a bridge in this "shortest-path graph". You can find those bridges with the standard algorithm.

To find the nodes that increase the distance, you can find the articulation points in this graph.

  • »
    »
    10 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    • The "shortest-path graph" will also be a directed graph right? How do we define bridges/ articulation mean?
    • Or do we include only those edges that are in a shortest s --> t path AND a shortest t --> s path make them undirected edges?
    • »
      »
      »
      10 месяцев назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
      • Yes, "shortest path graph" defined for a particular source is a DAG.
      • Let's call the required edges "special edges". Let's also consider only the subgraph $$$G$$$ of shortest path graph which includes only the nodes which can reach $$$t$$$ in the shortest path graph.

        Now special edges are essentially edges through which all paths from $$$s$$$ to $$$t$$$ in $$$G$$$ pass.

        How do we check if an edge $$$E : (u\rightarrow v)$$$ in $$$G$$$ is special? There is just one condition:

        Spoiler
      • Analogously defined vertices too, can be found in a similar manner. When checking for some vertex $$$x$$$, just check following:
        Spoiler

      So both the problems can be easily solved in $$$O(n\log{n})$$$.

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

      In the shortest-path graph all edges are directed away from S and towards T, so if an edge is a bridge when you undirect the edges it will also be a bridge in the DAG.

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

Interesting question, I don't know the answer but I like to suggest a similar problem: https://codeforces.com/gym/101741/problem/L