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.