Suppose you are given a directed graph G(V, E) with positive weights on the edges, as source vertex s and a destination t. Also, the graph has a special property - the shortest s − t path includes every other vertex in the graph.
Now the edges are vulnerable and can fail. So, you want to maintain alternate shortest path distances between s and t in case some edge e ∈ E fails. Design an O(E log V) algorithm that computes, for all e ∈ E, the shortest s − t path distance in the graph G \ e. Your final output should be an array of size E where the entry for edge e should contain the shortest s − t path distance in G \ e.
Replacement Path Problem on Directed weighted graph with a special property
hello @sahilkhan2312000131
pls share some of the sample test case with me.
also if problem link is given do share it with me
I don’t have test cases at this point. It’s more of a theoretical question, I am more concerned about the algorithm involved and how to construct it.
what i can think of is something like this->
a) run dijkastra from src and store distance of all vertex in some array fromSrcTo.
b) run dijkastra from destination and store distancr of all other vertex in some array fromDestTo.
now to calculate shortest distance by excluding edge (v1 to v2)
we can take help of the distance array.
shortest distance = fromSrcTo[v1] + alternate path from v1 to v2 + fromDestTo[v2]
as of now i can think of only upto this.
check this if this may help-> link
shortest distance = fromSrcTo[v1] + alternate path from v1 to v2 + fromDestTo[v2]
How will we calculate: alternate path from v1 to v2
will let u know if i get any logic
Here the shortest path is S→a→b→c→T
Consider the case where edge (b,c) is removed, now the shortest path becomes S→a→c→T
So your approach of finding an “alternate path from v1 to v2” fails, because we can’t be sure whether v1 and v2 will remain part of the new shortest path or not.
Also the research paper link you shared talks about undirected graph, while my question is related to Directed weighted graph with positive weights.
…
ur question has this constraint->
so they will make sure the graph has sufficient edges between vertices so that shortest path includes all vertices .
i shared it so that u get some idea about failure edges and vertices that will help u proceed furthur.
i am not having any other logic, if i will get any i will let u know
The special property that “the shortest s − t path includes every other vertex in the graph” holds true only in the initial graph G.
After the removal of any edge, the new graph doesn’t necessarily satisfy that property.
oh ok, only brute force approach is coming in my mind.
where u remove one edge and apply dijkastra on remaining.
its time complexity will be E^2log V.
or we can use bellman ford with some modification.
with dp state like this->
dp[i][j][k][l]-> shortest distance between i to j , without including edge k–>l
this we can do it easily.
but again its not Elogv.
dont know how we can optimise it to E log V
I found something similar on stackoverflow graph theory - algorithm to solve the replacement paths problem for specific situations - Stack Overflow
but i am not really getting it.
Please have a look if you are able to understand this.
dont know bro he is saying
Can u ask some other TA for help??
u can reopen the doubt …
The doubt is open from my side.
Have u marked it resolved??
…
no …, u need to reopen it so that other ta can take
How to reopen it?? It is showing open from my side
there must be some doubt reopen button in ur interface.
click on it.
if it is not their then u can create seprate thread using ask doubt button
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.