frying_pan's blog

Critical edges/ vertices in directed graph
By frying_pan, history, 16 months ago, In English

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?

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

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
16 months ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • 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?
    → Reply
    • »
      »
      »
      16 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it
      • 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})$$$.

      → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply