Rukashi's blog

Find all the edges that are a part of every shortest path
By Rukashi, 6 months ago, In English

So, here's the problem that I've came up with:

Given a undirected weighted graph, consisting of n vertices and m edges. The task is to find all the edges that are a part of every shortest path from vertex 1 to vertex n. In another word, find all the edges that if we delete it from the original graph, the shortest path from vertex 1 to vertex n will change or there will be no path from vertex 1 to vertex n .

Constraint: n <= 3 x 10^5, m <= min(3e5, n * (n — 1) / 2)

Here's my observation to this problem:

  1. First, we'll run Dijkstra in the original graph and find the shortest path from vertex 1 to vertex n. Let call it minimum_path.

  2. Define the cost of each edge is a pair {0, original_weight}.

  3. We'll run Dijkstra until the minimum cost it takes from vertex 1 to n is {x, minimum_path + y} (x and y are integer and y > 0). And after each time the function Dijkstra is called, we will trace all the edges on that shortest path and assign their value to {1, original_weight}. So the result is the value x in the last time y is equal to 0.

I think my solution is quite long and maybe incorrect, so I hope someone has a better solution to this problem.

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

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

If for some edge $$$u \to v$$$ the distance of $$$1 \to u \to v \to n$$$ (of course, each route being shortest) is equal to the distance of one shortest path, then that edge is part of one shortest path. The time complexity is equal to that of two Dijkstra runs, plus $$$O(E)$$$. That is $$$O((E+V)\log V)$$$ with binary heaps, or $$$O(E + V \log V)$$$ using fibonacci heaps.

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

    I think you're misunderstanding, the task is to find all the edges with each of them is a part of ANY shortest paths.

    Here's an example:

    8 8

    1 2 1

    2 3 1

    1 4 1

    4 5 1

    3 6 1

    5 6 1

    6 7 1

    7 8 1

    The answer is 2 (edges 6 — 7 and 7 — 8 because without one of them, the shortest path will change)

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
      ← Rev. 5   Vote: I like it +19 Vote: I do not like it

      Then you should have said ALL, not ANY. Anyways here is the solution that I believe should work for the ALL shortest paths case.

      During a Dijkstra run, track the previous node from each node. Then, you might visit some node with the same distance as visited last time. Find the cycle created by the edge, and contract the entire cycle into one vertex. Repeat for the entire Dijkstra run. This should take the same total time complexity with Dijkstra. The edges in the shortest path of the final graph are the ones in the intersection of all shortest paths.

      UPD: Actually, I've found a little flaw to this explanation, you shouldn't contract the cycle into one node, instead you should contract them to one directed path, and mark them as "not in the intersection". The gist is similar though.

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

        Thanks for your opinion. It was my bad in the word choice, it should be "every" instead of "any".

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

The task of finding necessary edges that belong to all shortest paths is similar to the CSES problem https://cses.fi/problemset/task/1203. The CSES problem asks us to find necessary vertices, nevertheless we can use the same solution here.

First, construct the directed acyclic graph (DAG) formed by edges which belong to a shortest path from 1 to n. This can be done via chromate00's first comment.

Next, our task reduces to finding edges which belong to all paths from 1 to n in this DAG. I believe this can be done via dp as in the CSES problem. (Edited: Originally posted an incorrect attempt)

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

    You can use a dp with high probability (it is like comparing hashes), but if you want deterministic you can just find bridges in the graph or apply dominator tree.

    → Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Here is my take, please correct if there is a mistake:

Claim: If $$$e$$$ is the $$$i\text{th}$$$ edge in a shortest path (from vertex $$$1$$$ to $$$n$$$), then it is the $$$i\text{th}$$$ edge in every such shortest path in which it occurs.

Proof: Otherwise we could find an even shorter path by combining the shorter sides of two given paths before and after $$$e$$$.

Solution idea: Run single source shortest path from vertex $$$1$$$ and from $$$n$$$. Save the distance to $$$1$$$ and to $$$n$$$ for each node as well as the total length of a shortest path $$$1\rightarrow n$$$. For each edge, inspect the distances of two incident vertices to determine if there is a shortest path going through this edge (2 possible directions to test for each edge). If this is the case, then the distance to vertex $$$1$$$ is the index of this edge in each shortest path with this edge.

Claim: An $$$i\text{th}$$$ edge in a shortest path is necessary if and only if it is the only $$$i\text{th}$$$ edge in the whole graph.

This is very easy to implement and its time complexity is not higher than that of the single source shortest path problem.

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

    Isn't your first claim wrong if the graph is weighted...

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

      You are right, I totally missed the fact that the graph is weighted. I don't see an easy way to adapt this to weighted graphs. :(

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

        Assuming weights are positive, can't you say that every shortest path edge occupies a segment $$$[l_i, l_i + w_i)$$$, and now an edge is used in every shortest path if and only if its segment doesn't intersect any other segments?

        → Reply
»
6 months ago, # |
← Rev. 3   Vote: I like it +20 Vote: I do not like it

So, first find all edges that are on any shortest path using Dijkstra's (I mean the union over all shortest paths). Delete all other edges. Now, the edges that are part of all shortest paths are exactly the bridges on this graph. Find them using DFS.

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

    Hey can you provide a basic sketch why it is working

    → Reply
    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      After removing non-shortest-path edges, we only have edges that are on some shortest path.

      A bridge is an edge that makes the graph disconnected when deleted. My claim is that not only the graph becomes disconnected, but nodes 1 and n become disconnected in particular.

      Let's prove it by assuming it's false and reaching a contradiction.

      If it's false, there is a bridge (u,v) that, when removed, doesn't disconnect 1 and n, meaning it leads to some biconnected component that is not in the path from 1 to n in the block-cut tree. This means that any path from 1 to n that crosses (u,v) must then come back and cross it in the opposite direction. At the same time (u,v) is on a shortest path from 1 to n, which is a contradiction, as no shortest path would cross over itself if weights are positive.

      This should be enough to prove that bridges are on all shortest paths.

      You can prove that non-bridges are not on all shortest paths by yourself.

      → Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it
  • To find the shortest path from vertex 0 to vertex ( N-1 ), you have two options.
  • Option 1: Go from 0 to ( u ), then from ( v ) to ( N-1 ), with the weight ( wt ) added.
  • Option 2: Go from 0 to ( v ), then from ( u ) to ( N-1 ), also with the weight ( wt ) added.

So, you're exploring two possible paths to find the shortest one from the start to the end vertex.

→ Reply
»
10 days ago, # |
  Vote: I like it +25 Vote: I do not like it

looks like leetcode copied your problem

→ Reply
»
10 days ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

My solution:
1. Find all the edges that are a part of any shortest path
2. Find a shortest path and save to an array
3. From all the other edges that are not part of the shortest path from step 2, form paths that start & end with nodes in the array. Save all (start_node, end_node) to a list
4. Remove all segment of (start_node, end_node) from the shortest path. This can be done by sorting segments & removing intervals
The remaining edges will be a part of every shortest path

→ Reply