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:
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.
Define the cost of each edge is a pair {0, original_weight}.
- 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.
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.
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)
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.
Thanks for your opinion. It was my bad in the word choice, it should be "every" instead of "any".
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)
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.
I was thinking of another approach. After we have constructed the graph formed by edges which belong to a shortest path from 1 to n, we can find the bridges of this newly formed graph. And, these bridges will be the answer to given problem.
Can you please check if my method is correct or not ? Thanks
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.
Isn't your first claim wrong if the graph is weighted...
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. :(
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?
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.
Hey can you provide a basic sketch why it is working
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.
So, you're exploring two possible paths to find the shortest one from the start to the end vertex.
looks like leetcode copied your problem
lol
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