0
$\begingroup$

Given a directed weighted graph, we need to mark all edges (represented by an ordered triple of (source,destination,weight) ) which lie on some shortest path from source to destination (there could be more than one shortest path);

I know that it can be done by running Dijkstra two times, first from source and another from destination with edges inverted. But i am not very clear about this algo so that i could implemment it,all i need a little description or explanation.... Thank You

|cite|improve this question
$\endgroup$
  • $\begingroup$ What do you mean by "mark" all vertices ? Dijkstra algorithm can find the shortest path in one run from source to sink not necessary by testing all paths. You just have to be careful that no edge has negative weight. $\endgroup$ – Vince Jan 22 at 9:17
  • $\begingroup$ What do you mean by " i am not very clear about this algo"? Do you want to have a proof/argument for the correctness? If so, this is on topic, but you may want to add what you have tried on your own. Are you looking for an implementation? Then this question is off-topic here. $\endgroup$ – Discrete lizard♦ Jan 22 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.